에라토스테네스의 체에 대해서
에라토스테네스의 체(Eratosthenes' Sieve)는 소수를 찾는 알고리즘입니다.
이 알고리즘은 고대 그리스의 수학자인 에라토스테네스에 의해 개발되었습니다.
에라토스테네스의 체는 2부터 시작하여 차례로 모든 수를 검사합니다.
소수인 수를 찾으면 그 수의 배수를 모두 제외시킵니다. 이 과정을 반복하여 최종적으로 남는 수들이 소수가 됩니다.
구체적인 동작 과정은 다음과 같습니다
2부터 시작하여 차례로 수를 증가시킵니다.
현재 수가 아직 제외되지 않았다면 소수로 간주합니다.
현재 수의 배수들을 모두 제외시킵니다. (자기 자신은 제외하지 않습니다)
모든 수에 대해 반복합니다.
예를 들어, 2부터 30까지의 소수를 찾을 때 에라토스테네스의 체를 사용하면 다음과 같은 과정을 거칩니다
2는 소수로 간주하고, 2의 배수를 모두 제외합니다. (2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30)
3은 소수로 간주하고, 3의 배수를 모두 제외합니다. (3, 6, 9, 12, 15, 18, 21, 24, 27, 30)
4는 이미 2의 배수로 제외되었으므로 넘어갑니다.
5는 소수로 간주하고, 5의 배수를 모두 제외합니다. (5, 10, 15, 20, 25, 30)
6은 이미 2와 3의 배수로 제외되었으므로 넘어갑니다.
7은 소수로 간주하고, 7의 배수를 모두 제외합니다. (7, 14, 21, 28)
8은 이미 2의 배수로 제외되었으므로 넘어갑니다.
9는 이미 3의 배수로 제외되었으므로 넘어갑니다.
10은 이미 2와 5의 배수로 제외되었으므로 넘어갑니다.
이러한 과정을 반복하면 2부터 30까지의 소수를 찾을 수 있습니다: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
위의 방식으로 알고리즘 코드를 작성해보겠습니다.
2 이상 n 이하의 정수 x가 소수인지 아닌지 구하면 여기서 배열의 이름을 sieve라고 하고, sieve[x] = 0 이면 소수이고, sieve[x] = 1이면 소수가 아니라는 의미로 정하겠습니다.
1. 초기에 크기가 n+1인 배열 sieve를 생성하고, 모든 원소를 0으로 초기화합니다. (sieve[x] = 0은 x가 소수라는 의미입니다.)
2. 2부터 시작하여 차례로 수를 살펴봅니다. (x라고 가정합니다.)
3. 현재 수 x가 아직 제외되지 않았다면 (sieve[x] = 0), x는 소수로 간주하고 x의 배수들을 전부 제외시킵니다. 이를 위해 sieve[x] = 1로 표시합니다.
4. x의 배수들을 제외시키는 과정은 x를 제외한 x의 모든 배수들에 대해 sieve[x] = 1로 표시하는 것입니다. (자기 자신은 제외하지 않습니다)
5. 모든 수에 대해 위의 과정을 반복합니다.
6. 반복이 끝나면, sieve 배열에서 값이 0인 인덱스들이 소수입니다.
for(int x = 2; x <= n; x++){
if(sieve[x] == 1) continue;
for (int u = 2*x; u<=n; u+=x){
// x가 소수였을 때, 그 다음 큰 배수부터 전부 1로 표시
sieve[u] = 1;
// ex) x가 3이면 6,9,12, ...를 전부 1로 표시
}
}초기에 sieve 배열: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2는 소수로 간주하고, 2의 배수들을 제외시킵니다. (sieve[2], sieve[4], sieve[6], ..., sieve[30] = 1)
3은 소수로 간주하고, 3의 배수들을 제외시킵니다. (sieve[3], sieve[6], sieve[9], ..., sieve[30] = 1)
4는 이미 2의 배수로 제외되었으므로 넘어갑니다.
5는 소수로 간주하고, 5의 배수들을 제외시킵니다. (sieve[5], sieve[10], sieve[15], ..., sieve[30] = 1)
6은 이미 2와 3의 배수로 제외되었으므로 넘어갑니다.
7은 소수로 간주하고, 7의 배수들을 제외시킵니다. (sieve[7], sieve[14], sieve[21], ..., sieve[28] = 1)
8은 이미 2의 배수로 제외되었으므로 넘어갑니다.
9는 이미 3의 배수로 제외되었으므로 넘어갑니다.
10은 이미 2와 5의 배수로 제외되었으므로 넘어갑니다.
이러한 과정을 반복하면 sieve 배열에서 값이 0인 인덱스들이 소수가 됩니다. 따라서, 2부터 30까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29입니다.
