에라토스테네스의 체 (Sieve of Eratosthenes)
이 방식은 지정됨 범위네에서 대량의 소수를 한번에 구할때 유용하다.
예를 들어 121 이하의 소수를 모두 구해야 한다고 해보자. 어떻게 해결해야 할까?
결론부터 말하면 121의 제곱근, 즉 11 이하의 소수 n에 대하여 n의 배수들은 전부 제외시키면 된다.
n의 배수라는 말 자체가 소수가 아니다.
아직 이해가 잘 안갈 수 있다. 다시 설명해 보자.
121의 제곱근인 11이하의 수 들을 생각해보자.
일단 2는 소수니 제거하지 않는다.
2를 제외한 모든 2의 배수 4, 6, 8, 10, ..., 120 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다.
3를 제외한 모든 3의 배수 6, 9, 12, ... 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다.
4는 아까 2의 배수에서 제거 됬으니 소수가 아니다.
5를 제외한 모든 5의 배수 5, 10, 15, ... 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다.
이를 그림을 통하여 확인해 보자.
C++ 구현
void Eratos(int n)
{
/* 만일 n이 1보다 작거나 같으면 함수 종료 */
if (n <= 1) return;
/* 2부터 n까지 n-1개를 저장할 수 있는 배열 할당
배열 참조 번호와 소수와 일치하도록 배열의 크기는
n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음) */
bool* PrimeArray = new bool[n + 1];
/* 배열초기화: 처음엔 모두 소수로 보고 true값을 줌 */
for (int i = 2; i <= n; i++)
PrimeArray[i] = true;
/* 에라토스테네스의 체에 맞게 소수를 구함
만일, PrimeArray[i]가 true이면 i 이후의 i 배수는 약수로 i를
가지고 있는 것이 되므로 i 이후의 i 배수에 대해 false값을 준다.
PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
소수가 아니게 된다. 그러므로 검사할 필요도 없다.
또한 i*k (k < i) 까지는 이미 검사되었으므로 j시작 값은 i*2 에서 i*i로 개선할 수 있다.
*/
for (int i = 2; i * i <= n; i++)
{
if (PrimeArray[i])
for (int j = i * i; j <= n; j += i)
PrimeArray[j] = false;
}
// 이후의 작업 ...
}
출처는 위키피디아 참고
'Algorithm > PS 알고리즘 정리' 카테고리의 다른 글
[알고리즘] Counting inversions (0) | 2022.01.21 |
---|---|
[알고리즘] lower_bound, upper_bound : C++ (0) | 2022.01.21 |
[알고리즘] 트리의 지름 : Diameter of Tree (2) | 2022.01.20 |
[알고리즘] Bipartite Graph : 이분 그래프 (0) | 2022.01.20 |
[알고리즘] Knapsack Problem (0) | 2022.01.20 |
댓글