[코딩테스트] 소수를 효율적으로 구해보자.
소수의 정의
소수의 정의는 1과 자기 자신으로만 나뉘어 지는 수이다.
이 말은 약수가 두개인 수라고도 할 수 있고,
2부터 N-1까지의 수로 나뉘어 지지 않는 수 라고도 할 수 있다.
이 정보만을 두고 보았을 때, 우리는 소수를 구하는 함수를 밑과 같이 짤 수 있다.
1
2
3
4
5
6
7
bool IsPrime(int _n){
if(_n == 1) return 0;
for(int i=2;i<_n;++i){
if(_n%i == 0) return 0;
}
return 1;
}
이 함수를 보면 바로 알 수 있듯이, 코드를 이렇게 짜면 시간 복잡도가 O(n)이 나온다.
이 구하는 방식은 매우 느리고, 코딩테스트에서 이 방법으로 소수를 구할려고 하면 대부분 시간 복잡도가 뜰 것이다. 그렇다면 어떻게 해야 시간 복잡도를 낮출 수 있을까? 다음의 정의를 읽어보자.
합성수 N에서 1을 제외한 가장 작은 약수는 $\sqrt{n}$ 이다.
이 정의를 일단 증명해보자.
- 합성수 N에서 1을 제외한 가장 작은 약수를 x라고 하자.
- N/x 또한 1이 아닌 N의 약수이기 때문에 x <= (N/x)가 성립한다.
- 우변의 분모 x를 좌변으로 옮기면 $x^2$ <= N이므로 x <= $\sqrt{n}$이 성립한다.
이렇게 증명했는데, 여기서 합성수의 증명을 생각해보자.
합성수란 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수이다.
즉 합성수란 소수의 반대되는 개념이라고 생각할 수 있다.
그렇다면 합성수 N에서 1을 제외한 가장 작은 약수는 $\sqrt{n}$이 증명을 거꾸로 생각해보면,
2부터 $\sqrt{n}$까지의 수로 나누어지지 않으면 소수인것이 아닐까?
이 정의를 가지면 소수를 더욱 효율적으로 구할 수 있다. 밑의 코드를 보자.
1
2
3
4
5
6
7
bool IsPrime(int _n){
if(_n == 1) return 0;
for(int i=2;i*i<=_n;++i){
if(_n%i == 0) return 0;
}
return 1;
}
이렇게 코드를 짜면 시간 복잡도를 O($\sqrt{n}$)까지 떨어뜨릴 수 있다.
지금까지의 방법은 어떤 수 N이 소수인지 아닌지 판별하는 것이었는데, 2~N까지중 소수인 수들이 어떤 것이 있는지 판별하는 방법도 있을까?
밑의 정의를 보자.
각 수의 1이 아닌 가장 작은 약수는 무조건 소수이다.
이 문장을 증명하기 위해 귀류법으로 증명해보겠다.
- 만약 어떤수 N이 소수가 아니라 합성수라고 가정해보자.
- 어떤수 d를 N의 가장 작은 약수라고 해보자.
- d가 소수가 아니라고 가정하면, d는 무조건 합성수여야 한다.
- d가 함성수라면 1 < m < d인 약수 m이 존재해야 한다.
- m이 d로 나뉘어짐으로, m은 n도 나눌 수 있다.
- 이는 m이 N의 가장 작은 약수라는 것인데, 2번의 정의에 의하면 d가 N의 가장 작은 약수여야 한다. 즉, d가 합성수라는 증명은 틀렸다!
그렇기에 d(가장 작은 약수)는 무조건 소수이다.
이 이론을 이용해서 소수 구하기를 더 개선할 수 있다.
소수를 구할 때 마다, vector에 저장해 놓고, vector에 있는 값들로만 현재 구하고자 하는 수를 나눠주면서 안 나눠지면, 그 수는 소수임을 판별하면 된다.
밑의 코드를 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> IsPrime(int _n) {
vector<int> primes;
for (int i = 2; i <= _n; ++i) {
bool isPrime = 1;
for (int p : primes) {
if (p * p > i) break;
if (i % p == 0) {
isPrime = 0;
break;
}
}
if (isPrime) primes.push_back(i);
}
return primes;
}
이 함수를 쓸경우 N이 5,000,000일때, 대략 0.4초가 걸린다.