소수판별 알고리즘 (에라토스테네스의 채)

소수 판별 알고리즘

---

시간 복잡도 O($N$)

소수는 약수가 1과 자기 자신 뿐인 수를 의미한다. 임의의 수 N이 소수인지 판별하는 가장 직관적인 방법은 2부터 N-1까지 나누어 떨어지지 않는다면 소수라고 판단할 수 있다.

boolean isPrime(int n) {
	// n이 2보다 작다면 실수가 아니다.
    if (N < 2) {
    	return false;
    }
    // 2부터 n-1 까지 나누어지는 수가 있는지 탐색
    for (int i = 2; i <= n-1; i++) {
    	if (n / i == 0) {
    		return false;
    	}
    }
    return true;
 }

위의 방법은 소수 하나를 찾는데 O($N$)의 시간이 걸리기 때문에 N개의 수 중에서 소수를 찾게 된다면 O($N^2$)의 시간이 걸리기에 실제로 사용하기에는 효율적이지 못한 알고리즘이라는 것을 알 수 있다.

시간 복잡도 O($N$) - $N/2$

24라는 숫자의 경우 가장 큰 약수가 12 이고 그 이상의 수는 2보다 작은 수와의 곱으로 표현되기 때문에 약수가 존재하지 않는다. 따라서 2부터 N-1까지가 아닌 N/2 까지만 검사하여 기존 방법보다 절반에 가까운 시간 복잡도를 가질 수 있다.

boolean isPrime(int n) {
	// n이 2보다 작다면 실수가 아니다.
    if (N < 2) {
    	return false;
    }
    // 2부터 n/2 까지 나누어지는 수가 있는지 탐색
    for (int i = 2; i <= n/2; i++) {
    	if (n / i == 0) {
    		return false;
    	}
    }
    return true;
 }

그러나 이 방법도 여전히 O($N^2$)의 시간복잡도는 벗어나지 못한다.

에라토스테네스의 채

시간 복잡도 O($Nlog(logN)$)

에라토스테네스의 채(채로 거르듯이 숫자들을 걸러서 채 라고 하는듯 하다) 알고리즘을 사용하면 O$(Nlog(logN))$ 의 시간복잡도로 N개의 수가 소수인지 판별 가능하다.

에라토스테네스의 채는 아래와 같은 과정으로 이루어진다.

1. 2부터 하나씩 지워져있는 수인지 아닌지 판별한다.
2. 수가 지워져있지 않다면 해당 수의 배수를 모두 지운다.

25까지의 자연수들 중 소수를 구해보자
우선, 지워지지 않은 가장 작은 수는 2이고, 2는 아직 지워지지 않았다. 따라서 2를 제외하고 2의 배수들을 모두 지운다 (2는 소수임을 확정)

	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

그 다음 3도 아직 지워지지 않았기 때문에 3을 제외한 3의 배수를 차례대로 지운다. (3 은 소수임을 확정)

	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

다음 4는 지워져있기 때문에 넘어가고( 4의 배수는 어차피 다 2의 배수) 그 다음 수 5는 지워지지 않았기 때문에 5를 제외한 5의 배수를 전부 지운다... (반복)

위와 같은 방법으로 O$(Nlog(logN))$의 시간복잡도로 자연수 N까지의 소수들을 판별할 수 있다.

소스코드 (Java)

boolean[] isPrime = new boolean[N+1];

for (int i = 2; i <= N; i++) {
	isPrime[i] = true;
}

for (int i = 2; i <= N; i++) {
	if(isPrime[i]) {
		for (int j = i * 2; j <= N; j += i) {
			isPrime[j] = false;
		}	
	}
}