[알고리즘/정수론] 에라토스테네스의 체 - C++

에라토스테네스의 체

Sieve of Eratosthenes

 

소수를 판정하기 위한 기본적인 정수론 알고리즘이다.

 

2부터 90까지의 수 중 소수를 구한다고 해 보자. (1은 소수가 될 수 없으므로 제외)

 

2를 확인하였을 때, 2는 소수이므로 이후 2의 배수는 모두 소수가 아닌 것으로 처리해준다.

 

3을 확인하였을 때, 3은 소수이므로 이후 3의 배수는 모두 소수가 아닌 것으로 처리해준다.

 

4를 확인하였을 때, 4는 이미 소수가 아닌 것으로 표시가 되어있으므로, 건너뛰고 5를 확인.

5를 확인하였을 때, 5는 소수이므로 이후 5의 배수는 모두 소수가 아닌 것으로 처리해준다.

모두 진행하게 되면 이와 같이 소수만 남게 된다.

이에 대한 코드는 아래와 같다.

bool prime[101] = {false};
// 100까지의 수 중에 소수를 표시하기 위한 배열
// false일 때를 소수, true일 때를 합성수로 표기
void sieve()
{
    for (int i = 2; i <= 100; i++)
    {
        if (!prime[i])
        {
            for (int j = 2 * i; j <= 100; j += i)
            {
                prime[j] = true;
            }
        }
    }
}