소수를 빠르게 찾는 방법
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);
}