에라토스테네스의 체 (Sieve of Eratosthenes) - soo:bak

개념

에라토스테네스의 체, Sieve of Eratosthenes 는 고대 그리스의 수학자 에라토스테네스가 처음으로 제안한 소수 를 찾는 방법입니다.

이 알고리즘은 특정 범위 내의 모든 소수를 찾는데 사용되며, 효율성과 간결함으로 인해 여전히 널리 사용되고 있습니다.

시간 복잡도는 O(n log log n) 으로, 소수 판별 알고리즘 중에서 가장 빠른 편에 속합니다.

알고리즘의 원리가 간단하여 이해하기 쉽고, 코드로 구현하기도 비교적 간편합니다.

따라서, 소수 찾기 문제에 있어서 기본적인 알고리즘으로 사용되고는 합니다.

원리 및 설명

에라토스테네스의 체의 시작 : 수열 생성

에라토스테네스의 체 는 먼저 2 부터 n 까지의 모든 자연수의 수열을 생성하는 것으로 시작합니다.

이 수열은 소수 판별의 ‘검사’ 대상이 됩니다.

숫자 1 은 소수의 정의에 부합하지 않기 때문에, 2 부터 검사를 시작합니다.

---

소수 찾기 : 배수의 제거

가장 작은 수인 2 를 소수로 간주하고, 이 숫자의 모든 배수 를 소수가 아니라고 판별합니다.

왜냐하면, 소수 는 ‘1 과 자기 자신 이외의 어떤 수로도 나누어 떨어지지 않는 수’ 이므로,

`2` 를 제외한 `2` 의 배수는 소수가 될 수 없기 때문입니다.

---

반복 : 소수 찾기와 배수의 제거

이제, 소수가 아니라는 판별 과정을 거친 후 남아있는 수들 중에서 다음으로 가장 작은 수를 선택하고, 이 수를 소수로 간주합니다.

마찬가지로, 이 숫자의 모든 배수 를 소수가 아니라고 판별합니다.

이 과정은 n 보다 큰 제곱수가 나오기 전까지 반복하게 되는데, 이유는 다음과 같습니다.

만약, 어떤 수가 소수가 아니라면, 이 수는 두 요소의 곱으로 표현될 수 있습니다.

이때, 두 요소 중 하나는 반드시 sqrt(n) 보다 크거나 같고, 다른 하나는 반드시 sqrt(n) 보다 작거나 같아야 합니다.

그렇지 않으면, 두 수의 곱은 n 을 초과하거나 n 보다 작아지게 되기 때문입니다.

따라서, 어떤 수가 소수인지 아닌지를 판단하는 것은 sqrt(n) 까지만 확인하면 충분하게 됩니다.

이 원리에 따라서, 에라토스테네스의 체 는 n 의 제곱근 까지만 고려 하게 되고,

이것이 에라토스테네스의 체 의 효율성에 핵심적인 역할을 합니다.

---

결과 : 소수의 추출

반복 과정이 끝나면, 남아 있는 모든 수들은 소수입니다.

남아있는 수들 각각은 앞선 과정에서 어떤 수의 배수로도 소수가 아니라고 표기되지 않았기 때문에, 이들 모두는 소수라고 간주할 수 있습니다.

---

구현

int n; // n 보다 작은 모든 소수를 찾는 예시

vector<bool> isPrime(n + 1, true); // 우선, 모든 수를 소수라고 가정
isPrime[0] = isPrime[1] = false; // 숫자 0과 1은 소수의 정의에 부합하지 않기 때문에 false 로 표기

for (int i = 2; i * i <= n; i++) { // 숫자 2부터 시작하여 n의 제곱근까지 범위 설정
  if (isPrime[i]) { // 만약, 아직 소수라고 표기된 상태, 즉 초기 상태 혹은 검사가 되지 않은 수인 경우
    for (int j = i * i; j <= n; j += i)
      isPrime[j] = false; // 배수에 대해서 소수가 아니라고 표기
  }
}

// 에라토스테네스의 체로 n 이하의 모든 자연수에 대한 소수 판별 완료.

for (int i = 0; i <= n; i++)
  if (isPrime[i])
    cout << i << "\n;"  // n 이하의 자연수들 중 소수로 판별된 모든 수를 한 줄마다 출력