내 잡다한 노트
에라토스테네스의 체 (소수 판별 알고리즘) 본문
에라토스테네스의 체의 쓰임새
- 소수를 대량으로 판별할 때 쓰인다.
시간 복잡도
- 어떤 숫자의 제곱근까지만 약수의 여부를 구하면 돼서 O(n^1/2)가 된다.
알고리즘
- 구해야 하는 소수의 범위로 배열을 할당
- 2부터 시작해서 배수인 숫자들을 지운다. 여기서 자기 자신은 지우지 않는다
- 이것을 전체 범위의 n^1/2까지 했다면 종료시킨다.
더 자세한 설명은 여기로!
그림으로 설명이 잘 돼있는 것 같다.
'알고리즘' 카테고리의 다른 글
| 트리, 최소공통조상(LCA, Lowest Common Ancestor) (0) | 2022.06.27 |
|---|---|
| Trie 트라이 알고리즘 (0) | 2022.05.14 |
| 동적 프로그래밍 D (0) | 2022.05.06 |
| 최대공약수와 최소공배수를 쉽게 구하는 유클리드 호제법 (0) | 2022.03.25 |
| 플로이드 와샬 알고리즘 (0) | 2022.03.23 |