소수를 빠르게 찾는 방법


작성일 : 2017-01-18 15:01:25
조회수 : 1814


본문

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)$ 이 됩니다.



#include<iostream>
using namespace std;

bool isPrime[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;
        }
    }
}
int main()
{
    int n;
    
    cout << "1000 이하의 수를 입력해 주세요.\n";
    cin >> n;
    sieveOfEratosthenes(n);
}

소수를 빠르게 찾는 방법 - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.