[Algorithm] 에라토스테네스의 체 (소수 판별)

개요

"에라토스테네스의 체" 알고리즘은 고대 그리스 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 "에라토스테네스의 체"라고 부릅니다.

 

주로 대량의 수에서 소수를 판별하기 위해서 사용되는 알고리즘이며, 종종 코딩테스트 문제에서 보이기에 정리해보는 시간을 가지게 되었습니다.

소수 판별 방법

소수는 1과 자기 자신 만을 약수로 가지는 수입니다.

 

만약 2에서 100 사이의 소수를 구해야 하는 문제라면 각각의 수의 약수가 존재하는지 확인하는 방법을 사용할 수도 있습니다. 하지만 위 방법을 사용하면 2부터 100사이의 모든 수를 순회하며 자신을 제외한 약수가 존재하는지 체크해야 하므로 매우 비효율적입니다.

 

약간 발상을 바꿔 생각해보면 결국 2 ~ 100 사이의 수 중에서 자기 자신을 제외한 [2의 배수, 3의 배수 ....]는 소수가 될 수 없으며, 이러한 방법을 사용하면 시간복잡도가 확연히 줄어들게 됩니다.

에라토스테네스의 체 작동 원리

알고리즘의 작동 원리를 간단히 단계별로 설명하면 다음과 같습니다.

1. 2부터 N까지의 수를 저장할 수 있는 배열을 생성합니다.
2. 2부터 N까지 자기 자신을 제외한 배수들을 체크합니다.
3. 배열을 순회하며 체크되지 않은 수(소수)를 확인합니다.

구현 예시

입력으로 N이 주어진 경우 2부터 N 사이의 소수를 판별하기 위한 코드를 작성해보도록 하겠습니다.

// 소수가 아닌 수를 체크하기 위한 배열
bool arr[1000002];

using namespace std;

int solution(int n) {
    int answer = 0;

    // 2부터 n까지의 수를 순회합니다.
    for (int i = 2; i <= n; i++)
    {   
        // 자기 자신을 제외한 배수들을 체크해줍니다.
        for (int j = i * 2; j <= n; j += i)
        {
            // 이미 체크된 수라면 넘어갑니다.
            if (arr[j] == 1) continue;

            // 체크된 수가 아니라면 체크해주도록 합니다.
            arr[j] = 1;
        }
    }

    // 소수가 아닌 수를 전부 체크했으므로 소수가 몇 개 존재하는지 체크합니다.
    for (int i = 2; i <= n; i++)
    {
        if (arr[i] == 0)
        {
            answer++;
        }

    }

    return answer;
}

참고 자료

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전