[백준 #1929 c++] 소수 출력하기, 그리고 에라토스테네스의 체의 시간복잡도

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

어떤 자연수 n까지의 소수를 모두 출력하라는 문제가 있을 때 일반적인 풀이 방법은 2부터 시작해서 그 수의 제곱근까지 mod 연산을 하여 소수 판별을 해주는 것이다.

 

이 작업은

 

​√1+√2​+√3​+...+√n

의 횟수를 가지며

 

1+1+1+...+1 = n < ​√1+√2​+√3​+...+√n < n+n+n+...+n = n²

 

즉 O(N) 보다는 크지만 O(N^2) 보다는 작은 어딘가에 있을 것이다.

 

하지만 시간복잡도를 더 줄일 수 있는 방법은 많은데 대표적인 예가 '에라토스테네스의 체'이다.

이 방법은 시간복잡도를 줄이는 대신 n공간 만큼의 배열을 만들어야 하기 때문에 공간복잡도가 O(n)이 된다.

---

에라토스테네스의 체로 소수를 구하는 방식을 보면

2부터 시작해서 √n까지 각 수의 배수들을 소수 배열에서 지우는 과정이 있다.

 

왜 n까지가 아니라 √n까지 구해도 될까?

 

예를 들어 121까지의 소수를 구한다면

121의 제곱근인 11을 초과하는 부분부터 살펴보자.

 

12x2, 12x3, 12x4..., 12x10

 

121보다 작거나 같은 수를 만들기 위해 곱해진 수 1~10은 모두 이전에 한 번씩 곱해진 수 들이기 때문에 반복할 필요가 없다.

 

반면 11을 포함해야 하는 이유는

11x11 = 121이며 11x11에서 11은 소수이므로 11 이전에 탐색한 모든 수로도 구할 수 없는 결과가 된다.

11x11은 소수가 아니므로 소수 배열에서 제외시키기 위해 11도 탐색해야하는 것이다.

---

여기서 한 번 더 탐색 횟수를 줄이는 방법이 있는데

√n까지 k의 배수들을 찾을 때

굳이 k를 제외한 k의 배수인 2k, 3k, 4k 가 아니라

k², k² + k, k² + 2k, k² + 3k.. 순으로 찾아도 된다.

 

이는 위와 같은 이유인데,

예를 들어 7을 제외한 7의 배수들을 소수 배열에서 지울 때

7의 배수인 14, 21, 28, 35 등은 각각 소인수 분해를 하면

7x2, 7x3, 7x4, 7x5가 되고 이는 역시 이전 단계인 2, 3, 4, 5 단계에서 모두 탐색을 했기 때문에 반복할 필요가 없는 것이다.

 

하지만 7x7 부터는 이전 단계에서 탐색을 하지 않았기 때문에 시작점을 7x7로 해서

7x7, 7x7 + 7, 7x7 + 14... 순으로 탐색을 하는 것이다.

 

이 과정을 포함하여 에라토스테네스의 체로 자연수 m부터 n까지의 소수를 출력하는 C++ 코드는 다음과 같다.

 

#include <iostream>
#include <cmath>
using namespace std;

bool pn[1000001];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int m, n;
	cin >> m >> n;
	int rtN = sqrt(n);
    	pn[1] = 1;
	// 에라토스테네스의 체
	for (int i = 2; i <= rtN; i++) {
		if (pn[i] != 0) continue;
		for (int j = i * i; j <= n; j += i) {
			pn[j] = 1;
		}
	}
	for (int i = m; i <= n; i++) {
		if (pn[i] == 0) cout << i << '\n';
	}
}

*전역에 선언된 배열 pn은 모두 false로 자동초기화되기 때문에 이를 이용하여 배열에서 제외시 true로 만들어주고 false인 경우만 출력하도록 할 수 있다.

 

 

다음은 핵심 내용인 위 코드의 시간복잡도이다.

n = 121일때,

2부터 √121까지 각 수의 배수를 배열에서 true로 만드는 동안의 과정은 다음과 같다.

 

4 6 8 10 12 14 16... 120 => 121/2 - (2 - 1) = 59
9 12 15 18 21... 120 => 121/3 - (3 - 1) = 38
4 pass
25 30 35 40 45 50... 120 => 121/5 - (5 - 1) = 20
6 pass
49 56 63 70 77... 119 => 121/7 - (7 - 1) = 11
8 pass
9 pass
10 pass
121 => 121/11 - (11 - 1) = 1

 

2의 배수인 4, 6, 8은 pass, 3의 배수인 9도 pass

이런 식으로 k가 소수인 경우에만 k², k² + k, k² + 2k, k² + 3k.. 순으로 탐색을 하는데

이 수열은 간격이 k 이므로 n/k번 탐색하지만

정확히는 k, 2k, 3k, 4k... k²-k 의 과정이 빠져있으므로 n/k - (k-1)번 이다.

 

이를 바탕으로 n에 대해 k가 소수인 부분의 탐색 횟수를 알아보면 다음 수열의 각 항들의 합과 같다.

 

n/2 - (2 - 1), n/3 - (3 - 1), n/5 - (5 - 1), n/7 - (7 - 1)... n/n^1/2 - (n^1/2 - 1)

 

하지만 항의 개수가 소수의 개수가 되고 이는

(n/2 + n/3 + n/5 + n/7 + ... + n/n^1/2) - (2 + 3 + 5 + 7 + ... + n^1/2) + (√n 이하의 소수의 개수 x 1)

=> n * (√n 이하의 소수의 역수의 합) - (√n 이하의 소수의 합) + (√n 이하의 소수의 개수)

로 정리할 수 있다.

 

탐색 자체는 √n번 하기 때문에 소수가 아닌 부분까지 더해주면 전체 탐색 횟수는

=> n * (√n 이하의 소수의 역수의 합) - (√n 이하의 소수의 합) + n

이 된다.

 

이 시간복잡도는 대략 O(Nlog(logN)) 에 해당하며

이 그래프는 다음과 같다.

 

이렇게 O(Nlog(logN)) 의 그래프는 O(n) 보다도 훨씬 밑에 있는 걸 확인할 수 있다.