에라토스테네스의 체 알고리즘 구현 방법

에라토스테네스의 체는 소수를 찾는 방법입니다.

고대 그리스 수학자 에라토스테네스가 발견하여 에라토스테네스의 체라고 이야기 하는데요.

원리는 다음과 같습니다.

먼저 0 과 1은 소수가 아니라고 마킹을 해 놓고 2부터 찾아 가면서 해당 수가 소수라면 소수의 배수들을 모두 너는 소수가 아니야 라고 마킹을 해 놓는 것입니다.

예를 들면 2를 만났을때 2의 배수 4,6,8,10,.... 등과 같은 모든 짝수들에 대해서 소수가 아니라는 것을 마킹하는 것이죠.

그리고 3을 만나면 3의 배수 6,9,12,15.... 등과 같이 3의 모든 배수들을 소수가 아니라고 마킹을 합니다.

4를 만나면 이미 소수가 아니라고 마킹이 되어 있기 때문에 그 배수들은 확인 할 필요가 없습니다.

5를 만나면 5의 배수들에 대해서도 마찬가지로 소수가 아니라고 마킹을 하는 방법입니다.

이렇게 체를 치는 방법을 C언어를 이용해서 구현해 보면 다음과 같습니다.

에라토스테네스의 체의 단점은 체를 치는 한계를 구해야 한다는 점과 마킹을 해야 하는 메모리를 할당을 해야 하는 부분입니다.

하지만 한번 소수를 마킹 해 놓는다면 소수를 구할때 마다 이 수가 소수인지 아닌지 판단할 필요가 없이 메모리에 마킹 되어 있는 부분만 확인하기 때문에 해당 범위의 소수의 갯수를 파악할때 유용하게 사용합니다.

만약 1부터 2000000 까지의 소수를 구한다고 생각하면 다음과 같이 구현해 볼수가 있습니다.

int prime[2000001]={1,1,0}; // prime 라는 소수 배열을 0과 1을 제외한 모든 배열을 0으로 셋팅합니다.
void eratos()
{
    for(int i=2;i<=2000000;i++) //i 에 대해서 체를 치기 위해서 2부터 2000000 까지 진행을 해 봅니다.
    {
        if(prime[i] == 0) //i가 소수라면 체를 칩니다.
        {
            for(int j= i*i; j<= 2000000;j+=i) prime[i]=1; 
            //여기서 i * i 부터 시작하는 이유는 i*i 이전의 수들은 그 이전에 이미 체를 친 경우입니다. 
            //만약 i 가 5 라면 25부터 시작해도 되는 이유는 그 이전의 수들은 2,3 에 의해서 이미 처리가 된 경우이기 때문입니다.
        }
    }
}