소수

소수란?

 

소수란 약수가 1과 자기 자신 밖에 없는 수다

 

소수와 관련된 알고리즘은 두가지가 있다

 

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법

2. N 이하의 모든 자연수 중에서 소수를 찾아내는 방법

 

나누어서 알아보자

 

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법

 

소수란 약수가 1과 자기 자신 밖에 없는 수니

2 이상이고 자기 자신보다 작은 수로 나누어 떨어지면 안된다.

 

이런 특성을 코드로 표현하면 아래와 같다

 

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

 

이는 O(N)의 시간복잡도를 가진다.

 

나쁜 방법은 아니지만 이를 조금 더 개선할 수 있는데

N-1까지 나눠보지 않고 N/2까지만 나눠보는 것이다.

어차피 N의 약수 중에서 가장 큰 것이 N/2보다 작거나 같기 때문!

 

따라서

 

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

 

이렇게하면 탐색 범위를 줄일 수 있다

그러나 이도 결국 O( N/2 ) 이기에 O(N)과 같다

 

하지만 괜찮다.

이를 O (루트 N) 의 시간 복잡도를 가지게 범위를 더 줄일 수 있다.

 

어떤 수 N이 있다면 이 수가 소수인지 판별하기 위해선 N의 제곱근까지만 검사해줘도 되기 때문에

 

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

 

이렇게 i * i <= n 으로 n의 제곱근을 표현해 알고리즘을 만들면

매우 빠르게 입력된 수가 소수인지 판별 할 수 있다

 

2. N 이하의 모든 자연수 중에서 소수를 찾아내는 방법

 

이럴 때는 1과는 다른 방법을 사용하는 게 좋다.

 

활용할 수 있는 다른 방법으로는 에라토스테네스의 체라는 것이 있는데 

N이하의 모든 자연수 중에서 소수를 찾는다고 하면

N까지의 모든 자연수를 가지고 있는 상태에서

2부터, 이 수를 i라고 하면 i * i 가 N보다 커지기 전까지 자신을 제외한 모든 배수를 지우기를 반복하는 것이다.

 

코드로 구현하면

 

int prime[n]; // 소수 저장 배열
int pn = 0;    // 소수의 개수
bool check[n+1] // 지워지면 true
 
for(int i=2; i<=n; i++{
        // 들어올 수가 소수면    
    if (check[i] == false) {
        // 소수 배열에 추가하고
        prime[pn++] = i;
        // 소수의 다음 배수부터 N보다 작을때까지 지워준다.
        for( int j = i + i; j <= n; j += i) {
            check[j] = true
        }
    }
}