소수를 빠르게 찾는 방법

1과 자기 자신으로만 나누어지는 수인 소수를 구하는 문제는 알고리즘 면접 문제로 보기 제격인 문제입니다. 소수 판별을 하는 방법에는 많은 방법이 있지만, 여기서는 간단하고 쉽게 짤 수 있는 에라토스테네스의 채에 대해 알아보겠습니다.

에라토스테네스의 채의 원리는 간단합니다. 소수를 판별하기 위해 n 이하의 배열을 선언합니다. 그 다음, 배열에 1번도 방문한 적 없다면 그 수를 소수로 출력하고, 그 수의 배수들을 전부 방문 체크 해주면 됩니다. 이를 그림으로 표현하면 다음과 같습니다.

(출처 : 위키백과)

이제 이것을 소스코드로 구현 해보겠습니다. 언어는 C++로 진행하겠습니다.

bool isPrime[1001];
void sieveOfEratosthenes(int n)
{

}

isPrime 배열은 n의 최댓값이 1000이라는 가정하에 1000까지 검사하기 위하여 1001칸을 선언하였습니다. 이제 함수 안의 내용을 작성해 봅시다. 위에 적었던 내용을 그대로 소스코드에 옮겼습니다.

void sieveOfEratosthenes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        /*방문한 적 없다면 소수이다.*/
        if (isPrime[i] == false)
        {
            cout << i << " ";
            /*이 수의 배수는 소수가 아님이 자명하므로 모두 방문처리해준다.*/
            for (int j = i * 2; j <= n; j += i) isPrime[j] = true;
        }
    }
}

그리고 main 함수에 검사를 할 수 있도록 위의 함수를 호출합니다.

int main()
{
    sieveOfEratosthenes(1000);
}

결과를 확인해 보겠습니다.

정상적으로 소수가 출력됨을 알 수 있습니다.

이 알고리즘의 시간 복잡도는 어떻게 될 까요? 어떠한 소수에 대해, n 이하에서 소수의 배수들을 모두 체크해 주므로 for문의 반복 횟수가 $(n/2 + n/3 + n/5 + n/7 + n/11 + ...)$ 로 갑니다. 이를 시간 복잡도로 표현하면 다소 복잡한 $O(n log logn)$ 이 됩니다.