[알고리즘] O(sqrt(N)) 소수 판정 알고리즘

소수는 1보다 크고 1과 자기 자신으로만 나눠지는 자연수입니다.

 

자연수 N이 소수임을 판별하는 방법은 2부터 n-1까지의 자연수로 자연수 N을 나눴을 때 나누어 떨어지는지 보면 됩니다.

 

만약 2부터 n-1까지의 자연수 중에 하나라도 나누어 떨어지면 자연수 N은 소수가 아닙니다.

 

그런데 이렇데 n-1까지 나누어 보는 방식은 O(N)의 시간 복잡도가 걸립니다.

 

n-1까지 나누어 떨어지는지 다 확인할 필요가 없고 sqrt(N)까지만 나누어 봐도 소수임을 판별할 수 있고 이때 시간 복잡도는 O(sqrt(N))입니다.

 

 

<C++ 소스 코드>

#include <iostream>
using namespace std;
 
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
 
int main(void) {
    cout << "input N : ";
    int n;
    cin >> n;
    if (isPrime(n)) {
        cout << n << " is prime number";
    }
    else {
        cout << n << " is composite number";
    }
    return 0;
}
 

<증명>

자연수에서 두 개 이상의 소수의 곱으로 이루어져 있는 수, 1과 소수를 제외한 수를 합성수라고 합니다.

 

어떤 수가 합성수가 아님을 판별하면 그 수는 소수입니다.

​

자연수 N을 N = P X Q (P <= Q, P 와 Q 는 1과 N이 아닌 자연수)을 만족하는 합성수라고 가정했을 때

​

N = P X Q >= Q x Q = Q ^ 2

-> Q <= sqrt(N)

 

따라서 N은 sqrt(N)보다 작은 적어도 하나의 인수를 가지므로 sqrt(N)까지만 나누어보면 됩니다.