[수학]Sieve of Eratosthenes

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

최적화된 소수 구하기 알고리즘

예시 코드

int number = 10000; // 구하고자 하는 소수의 범위 (배열 최대 크기를 넘어가지 않게 주의)
bool notPrime[10001];

void primeNumberSieve(){
    // 초기화. 0, 1은 소수가 아니다.
    for (int i = 2; i <= number; i++)    notPrime[i] = false;

    for (int i = 2; i <= sqrt(number); i++){
        // prime[i] 가 0이면 이미 소수가 아니므로 continue
        if (notPrime[i])    continue;
        
        for (int j = i * i; j <= number; j += i)    notPrime[j] = true;
    }

    // 소수 출력
    for (int i = 2; i <= number; i++){
        if (!notPrime[i])    printf("%d\n", i);
    }
}