에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체(Sieve of Eratosthenes)란?

에라토스테네스의 체는 특정 범위 내의 모든 소수(Prime Number)를 빠르고 효율적으로 찾아내는 알고리즘입니다. “소수가 아닌 수(합성수)는 그 수의 제곱근보다 작거나 같은 소인수를 가진다” 는 원리를 이용합니다. 즉, 소수의 배수들을 순차적으로 제거해나가면 최종적으로 소수만 남게 됩니다.

---

동작 방식

1. 배열 초기화: 찾고자 하는 범위(2부터 N까지)의 모든 수를 담는 배열을 생성하고, 모두 소수(true)라고 가정하여 초기화합니다.

2. 배수 제거: 2부터 시작하여, 해당 숫자의 배수들을 배열에서 모두 제거(false로 변경)합니다. 이 과정을 N의 제곱근까지 반복합니다.

   • 예를 들어, 2의 배수(4, 6, 8, …)를 모두 제거합니다.
   • 다음으로, 3의 배수(6, 9, 12, …)를 모두 제거합니다.
   • 이때, 이미 제거된 숫자는 건너뜁니다.

3. 소수 판별: 과정 2가 끝난 후에도 배열에 소수(true)로 남아있는 수들이 바로 해당 범위의 모든 소수입니다.

---

코드

#include <iostream>
#include <vector>
#include <cmath>
 
// n 이하의 모든 소수를 찾는 함수 (에라토스테네스의 체)
std::vector<int> sieve_of_eratosthenes(int n) {
    // 2부터 n까지의 모든 수를 소수로 가정 (true로 초기화)
    std::vector<bool> primes(n + 1, true);
    primes[0] = primes[1] = false;
 
    // n의 제곱근까지만 반복 (i*i <= n 은 i <= sqrt(n) 보다 효율적)
    for (int i = 2; i * i <= n; ++i) {
        // i가 소수라면
        if (primes[i]) {
            // i의 배수들을 모두 소수에서 제외
            // (시작점을 i*i로 하는 최적화 적용)
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
 
    // 소수 목록을 결과 벡터에 담기
    std::vector<int> prime_numbers;
    for (int i = 2; i <= n; ++i) {
        if (primes[i]) {
            prime_numbers.push_back(i);
        }
    }
    return prime_numbers;
}
 
int main() {
    // 100까지의 소수 찾기
    std::vector<int> result = sieve_of_eratosthenes(100);
 
    // 결과 출력
    for (int p : result) {
        std::cout << p << " ";
    }
    std::cout << std::endl;
 
    return 0;
}