Post

[코딩테스트] 소수를 효율적으로 구해보자.

소수의 정의

소수의 정의는 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}$ 이다.

이 정의를 일단 증명해보자.

  1. 합성수 N에서 1을 제외한 가장 작은 약수를 x라고 하자.
  2. N/x 또한 1이 아닌 N의 약수이기 때문에 x <= (N/x)가 성립한다.
  3. 우변의 분모 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이 아닌 가장 작은 약수는 무조건 소수이다.

이 문장을 증명하기 위해 귀류법으로 증명해보겠다.

  1. 만약 어떤수 N이 소수가 아니라 합성수라고 가정해보자.
  2. 어떤수 d를 N의 가장 작은 약수라고 해보자.
  3. d가 소수가 아니라고 가정하면, d는 무조건 합성수여야 한다.
  4. d가 함성수라면 1 < m < d인 약수 m이 존재해야 한다.
  5. m이 d로 나뉘어짐으로, m은 n도 나눌 수 있다.
  6. 이는 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초가 걸린다.

This post is licensed under CC BY 4.0 by the author.