[알고리즘] 가장 빠른 소수 구하기 - 에라토스테네스의 체

1. 소수 구하기 알고리즘에 대하여

알고리즘을 공부하는 사람이라면 누구나 소수를 찾는 문제에 직면하게 된다.

가장 쉽게는 가능한 모든 수 범위에서 소수를 구할 수 있지만, 범위가 클 경우 시간이 매우 오래 걸린다.

그러므로 큰 범위에서 소수를 찾기 위해서는 효율적인 알고리즘을 사용할 필요가 있는데,

여기에서 알아볼 알고리즘이 '에라토스테네스의 체' 이다.

 

 

 

2. 에라토스테네스의 체

'에라토스테네스(Eratosthenes)의 체'란, 다음과 같이 반복적인 과정을 반복함으로서

주어진 범위에서의 소수를 찾는 것이다.

 

'에라토스테네스의 체'의 동작 과정

(1) 2부터 시작해, 2를 제외하고 2의 배수들을 모두 제외시킨다.

(2) 3부터 시작해, 3을 제외하고 3의 배수들을 모두 제외시킨다.

(3) 4는 이미 제외되었으므로, 5부터 시작하고 5를 제외하고 5의 배수들을 모두 제외시킨다.

(4) 6은 이미 제외되었으므로, 7부터 시작하고 7을 제외한 7의 배수들을 모두 제외시킨다.

 

위의 과정을 지속적으로 반복하면 남아있는 수들이 소수가 된다.

참고로 여기에는 다음과 같은 테크닉을 이용해 계산을 빠르게 할 수 있다.

 

- N이 소수인지는 판별하려면 루트 N 까지만 나누어서 0으로 나누어 떨어지지 않으면 된다는 사실

- 범위를 증가시킬 때 1씩 증가시키는 것이 아닌, 배수씩 증가시키는 테크닉

 

 

 

3. 구현

#include <iostream>
#include <cmath>
#include <string.h>

using namespace std;

int main(void)
{
	int N;
    cin >> N;
    
    bool *arr = new bool[N+1];
    memset(arr, 1, sizeof(bool) * (N+1));
    
    int root = sqrt(N);
    
    for(int i = 2; i <= root; i++)
    {
    	if(arr[i])
        	for(int j = i + i; j <= N; j += i)
            	arr[j] = false;
    }
    
    for(int i = 2; i <= N; i++)
    	if(arr[i]) cout << i << '\n';

	return 0;
}