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

에라토스테네스의 체로 소수를 구하는 gif

(위키백과)

 

소수: 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수

에라토스테네스의 체: 어떤 범위 내의 소수를 구하기 위해서는 이전까지 한 번도 어떤 수의 배수가 아니었던 수를 소수로 결정하고 그 수의 배수를 지워나가면 된다.

 

int main() {
    bool chk[100001];
    bool prime[100001] = { false };
    for(int i=2;i<=100000;i++){
        if (chk[i] == true) continue;
        chk[i] = true;
        prime[i] = true;
        int n = 2;
        while (n*i<=100000) {
            chk[n*i] = true;
            n++;
        }
    }
    
    return 0;
}

2부터 100000까지 모든 소수를 표시해주는 코드

 

실행 과정

1. 2, 3번 줄 // 모두 false인 100001칸짜리 (0 고려) 배열 선언
2. 4번 줄 // i는 지금 확인할 수 (2부터 100000까지)
3. 8~12번 줄 // n=2부터 시작, 100000안에 있는 모든 i의 배수의 chk는 true, prime은 false로 하여 방문은 했으나 소수는 아닌 것으로 기록
4. 5번 줄 // 만약 chk[i]가 true라면 이 수는 이미 방문한(소수이거나 소수가 아닌 것으로 판단 된) 수이므로 continue 
5. 6~7번 줄 // chk가 false라면 위의 3, 4번에서 걸러지지 않고 온 것이므로 chk를 true로 해주고(방문 표시) prime도 true(3번에 걸리지 않았으므로)

 

그냥 적으니 상당히 난해한데 위의 gif와 대응해보자면

5번은 처음 오른쪽에 숫자 i를 적고 색깔을 칠하는(chk을 true로 만드는) 것

3번은 이후 오른쪽에 숫자를 적지 않고 색칠만 하는(chk을 true로 만드는) 것

4번은 다음 숫자로 넘어갈 때 색칠된 숫자를 피하는 것

이 되겠습니다