소수 판별 알고리즘과 에라토스테네스의 체

소수 판별 알고리즘

소수 판별 알고리즘은 시간복잡도에 따라 다르게 구현 가능하다.

 

시간 복잡도 O(N)

소수란, 약수가 1과 자기자신 뿐인 수를 말한다. 따라서 N이 소수인지 판별하는 가장 쉬운 방법은 2부터 N-1까지의 수로 나누어 떨어지는지 확인하고, 나누어 떨어진다면 소수가 아니라고 판단하는 것이다.

 

bool isPrime(int N) {
    if (N < 2) return false;
    for (int i=2; i<=N-1; i++) {
    	if (N/i == 0) return false;
    }
    return true;
}

 

그러나 위 방법의 시간복잡도는 O(N)으로, 비교적 시간이 오래걸리는 알고리즘이다. 

 

 

시간복잡도 O(N), T(N) = N/2

N이 1과 자기 자신을 제외한 약수를 가지고 있다고 할 때, 해당 약수들은 2, 3, 4, ..., N/4, N/3, N/2 중에 존재한다. 따라서, N의 약수 중 최대 수는(N은 제외) N/2 가 된다. 2~N-1 까지 모두 검사할 필요 없이, 2~N/2 까지의 수만 검사하면 O(N/2) 의 시간복잡도로 문제를 해결할 수 있다.

 

bool isPrime(int N) {
    if (N < 2) return false;
    for (int i=2; i<=N/2; i++) {
    	if (N/i == 0) return false;
    }
    return true;
}

 

 

시간복잡도 O(루트 N)

위의 두 방법보다 더 빠른 알고리즘이 있다.

N = a * b (a <= b) 라 할 때, a = 1, 2, 3, ..., 루트 N 이면 자동적으로 b = 루트 N, .... , N/3, N/2, N 이 된다.  이 때, a 가 될 수 있는 수들로만 나누어떨어지는지 확인하면, 나머지 약수들은 자동적으로 확인이 된다. 따라서, 2~루트 N까지만 검사하여 O(루트 N) 의 시간복잡도로 문제를 해결할 수 있다.

 

bool isPrime(int N) {
    if (N < 2) return false;
    for (int i=2; i*i<=N; i++) { //(i < 루트 N) 은 (i*i < N) 으로 표현
    	if (N/i == 0) return false;
    }
    return true;
}

 

 

 

에라토스테네스의 체

1부터 N까지의 수 중 소수를 구하기 위해, 위의 isPrime() 함수를 사용할 수 있다.

 

for (int i=2; i<=N; i++) {
	if (isPrime(i)) printf("%d ", i);
}

 

그러나 해당 방법의 시간 복잡도는 O(N루트N)으로 비교적 오래걸린다. 에라토스테네스의 체 알고리즘을 사용하면 시간 복잡도 O(NloglogN) 내에 모든 소수를 구할 수 있다. 에스토스테네스의 체는 다음과 같은 과정을 거친다.

 

1) 지워지지 않은 가장 작은 수를 찾는다.

2) 해당 수는 소수이다.

3) 해당 수의 배수들을 모두 지운다.

 

N = 100 이라 가정할 때, 1 ~ 100 까지의 자연수들 중 소수를 구해보자.

먼저, 지워지지 않은 가장 작은 수는 2이고, 이는 소수이다. 2를 소수로 확인한 뒤, 2의 배수들을 모두 지운다.

 

 

 

 

이후, 지워지지 않은 가장 작은 수는 3이고, 이는 소수이다. 이후 3의 배수들을 모두 지운다.

 

 

 

이후, 지워지지 않은 가장 작은 수는 5이고, 이는 소수이다. 이후 5의 배수들을 모두 지운다. 

 

 

 

이후, 지워지지 않은 가장 작은 수는 7이고 이는 소수이다. 이후 7의 배수들을 모두 지운다.

 

 

이를 반복하면, 최종적으로 100 이하의 소수 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 이 도출된다.

 

 

전체 코드

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>
using namespace std;

int N = 100;
vector<bool> vcheck(105, true);

int main() {

    vcheck[1] = false;
    for (int i=2; i*i<=N; i++) { //i<=N 최적화 
        if (!vcheck[i]) continue;
        for (int j=i*i ; j<=N; j+=i) //j=2*i 최적화
            vcheck[j] = false;
    }
	return 0;
}

/*에스토스테네스의 체 최적화
i의 배수를 지우기 위해서는 i*i부터 확인하면 됨
i*i 미만의 수들의 경우, 가장 작은 약수는 i미만일 것이므로 이미 다른 수의 배수로 지워져있음
*/