소수 판정 알고리즘

소수 판정 알고리즘

1. 1개의 수만 판정할 때 : $O(n^{0.5})$

bool isPrime(int n){
    if(n <= 1) return false;
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0) return false;
    }
    return true;
}

 어떤 한 수가 소수인지 아닌지 알고 싶을때는 위와 같이 돌리면 된다. $\sqrt{n}$까지 검사하는 이유는 "2...$\sqrt{n}$까지 나눴을 때 n의 약수가 없다면 n은 소수다"이기 때문이다. 이 증명법은 "약수, 소인수분해 알고리즘" 포스트에서 증명한

 

자연수 n에 대해 n의 어떤 약수 x와 n/x에 대해 min(x, n/x) <= $\sqrt{n}$이다.

에서

 

2...$\sqrt{n}$까지 나눴을 때 n의 약수가 없다면 n은 소수다

를 유도할 수 있다. 증명 과정은 간단하다. "2 ... $\sqrt{n}$ 중 n의 약수가 없다면 n은 소수다."의 대우는 "n이 소수가 아니라면(합성수라면) 2 ... $\sqrt{n}$ 중 n의 약수가 존재한다" 인데, 이는 위에서 이미 보인 사실이다.

 

 

 

2. 에라토스테네스의 체 - 여러개의 수를 판정할 때 : $O(nloglogn)$

typedef long long ll;
// isPrime[i] : i가 소수이면 true, 아니면 false.
 
void find_prime_basic(vector<bool>& isPrime, ll max_value){
    vector<bool> isPrime(max_value, true);
    isPrime[0] = isPrime[1] = false;
    for(ll i = 2; i<=max_value; i++){
        if(isPrime[i]){
            for(ll j = i*2; j<=max_value; j+= i){
                isPrime[j] = false;
            }
        }
    }
}

지워지는 숫자의 개수는
i가 2일 때 : 2, 4, 6, 8, ... 제거 -> $\tfrac{n}{2}$개 숫자 지워짐(그만큼 연산함)
i가 3일 때 : 3, 6, 9, 12, ... 제거 -> $\tfrac{n}{3}$개의 숫자가 지워짐(그만큼 연산함)
...
이렇게 반복된다. 

 

소수의 역수의 합(Harmonic progressiong of the sum of primes)은 log(log(n))이다.

따라서 - n($\tfrac{1}{2} + \tfrac{1}{3} + \tfrac{1}{5} + ...$) = $n(loglogn)$이다.

따라서 시간복잡도는 $O(nloglogn)$이다.

 

 

typedef long long ll;
// isPrime[i] : i가 소수이면 true, 아니면 false.
 
void find_prime_improved(vector<bool>& isPrime, ll max_value){
    vector<bool> isPrime(max_value, true);
    isPrime[0] = isPrime[1] = false;
    for(ll i = 2; i<=sqrt(max_value); i++){
        if(isPrime[i]){
            for(ll j = i*i; j<=max_value; j+= i){
                isPrime[j] = false;
            }
        }
    }
}

 향상된 버전으로는 바로 위 코드와 같다. 이 경우, max_value보다 작은 소수를 구하기 때문에 기존 소수 판정과 동일하게 outer for loop는 $\sqrt{n}$까지 반복한다. max_value보다 작은 모든 수 x 중 2, ... , $\sqrt{x}$까지 나눴을 때 x의 약수가 없다면 x는 소수인 것으로 판정할 수 있는데, 모든 x에 대해 $\sqrt{x}$ < $\sqrt{n}$이기 때문이다. (자명한 이유다)

 또, inner for loop의 j를 2i가 아니라 i*i부터 시작해도 된다. 왜냐하면, 2, ... , i-1의 모든 배수 k는 이미 isPrime[k] = false로 처리되었기 때문이다. 조금 풀어 쓰자면, inner for loop j가 2i부터 시작되는 경우 2i, 3i, 4i, ... , (i-1)i, i*i, (i+1)i, ... 로 나아가는데 2i의 경우 2의 배수, 3i의 경우 3의 배수, ... (i-1)i는 (i-1)의 배수로 이미 지워진 상태이기 때문이다.

 신경써야 할 것은 inner, outer for loop의 i, j가 범위를 초과하지 않도록 범위계산을 미리 해 둬야 하는 것이다.