본문 바로가기
Algorithm

[알고리즘] 소수 판별법

by 방준이 2021. 9. 13.
반응형

[알고리즘] 소수 판별법

소수(prime number) 란? 

소수 (Prime Number)는 1과 자기 자신으로만 나누어떨어지는 자연수를 뜻한다. 좀 더 수학적인 표현을 사용한다면 정수 p > 1의 양수인 약수가 1과 p뿐일 때, p를 소수라고 부른다. 가령 자연수 7의 경우 1과 7로만 나누어 떨어지므로 소수이다. 다른 예로 자연수 4의 경우 1, 2, 4로 나누어 떨어지므로 소수가 아니다. 그렇다면 소수에 대해서 알았으니 소수판별법에 대해서 알아보자.

 

소수판별법

수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다.

 추가로, 합성수(合成數, composite number)는 1보다 큰 자연수 중에서 소수가 아닌 수로 합성수의 특징은 약수의 개수가 3개 이상이고 둘 이상의 소수를 곱한 자연수이다. -위키백과 -

 

소수판별법 구현 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class PrimeTest {
    public static void main(String[] args) {
        int num = 16;
        if(isPrime(num)) System.out.println(num + "은 소수 입니다.");
        else     System.out.println(num + "은 소수가 아닙니다.");
        
    }
    public static boolean isPrime(int num) {
        if (num <= 1return false;    // 1은 소수가 아니다.    
        if (num <= 3return true;    // 2와3은 소수이다.
        for(int i = 2; i <= num -1; i++) {
            if(num % i == 0return false;
        }
        return true;
    }
}
 
 
 

 

 위와 같은 코드는 1과 자기 자신으로만 나누어 떨어진다는 소수의 정의를 이용해서 빠르게 구현해 볼 수 있는 코드이다. 하지만, 조금 더 효휼적인 방법이 존재한다. 참고로 위 코드의 시간복잡도는 O(n) 이다.

 

소수판별 효율적인 방법

 사실, 소수를 판별하는데 있어서 조금 더 효율적인 풀이가 존재한다. 시간 복잡도 : O(√n) 으로 말이다.

가령 자연수 10037을 소수판별하기 위해서는 위의 코드의 경우 10037번 정도 반복문을 반복해야 하지만 아래 코드의 경우 단, 100번 정도 반복하면 소수인지 판별 할 수 있다. 아주 효율적이지 않은가? (참고로 10037은 소수이다.)

Theorem. n > 1이 합성수이면, n은 p <= √n 인 소인수 p를 갖는다.

이를 증명하기 위해서 한 가지 알아야할 Lemma 가 있다.

정수 n > 1의 양수인 약수들 중에서 1을 제외하고 가장 작은 것을 p라고 하자. 그렇다면 p는 소수이다.

 

prof. ) 귀류법을 이용해서 위의 Lemma를 증명해보자. (참고로 귀류법은 명제의 결론을 부정하면 모순이 일어남을 보여 명제가 참임을 증명하는 방법을 귀류법이라 한다.) 만약 p가 소수가 아니라면 p가 다른 값으로 나누어 질 수 있다는 뜻이 된다. 즉 1 < q < p인 약수 q를 갖는다. 이 q는 n의 약수이기도 하다. 앞서서 1을 제외한 가장 작은 약수를 p라고 정의했지만 이는 모순이 되므로 Lemma는 참이된다.

 

증명하고자 하는 정리는 Theorem. n > 1이 합성수이면, n은 p <= √n 인 소인수 p를 갖는다.

위의  Lemma를 이용해서 Theorem을 증명해보자.

 

prof. ) n>1인 약수들 중에서 1을 제외하고 가장 작은 것을 p라고 하면 (앞서 살펴본 Lemma.에 의해 ) p는 소수이다. 그렇다면 n = pm 이다. n은 합성수이므로 1 < p <= m < n이 성립함을 알 수 있다. 따라서 $p^{2}$ <= pm = n, 즉 p <= √n이다.  정리하여 소수관점에서 본다면 정수 n > 1이 √n 이하의 어떠한 소수로도 나누어지지 않으면 n은 소수이다. 가령 16의 경우 2부터  √16 = 4 이하의 어떠한 어떠한 수로도 나누어지지 않으면 n은 소수이다.

 

 

소수판별법 구현 - 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class PrimeTest2 {
    public static void main(String[] args) {
        int num = 16;
        if(isPrime(num)) System.out.println(num + "은 소수 입니다.");
        else     System.out.println(num + "은 소수가 아닙니다.");
        
    }
    public static boolean isPrime(int num) {
        if (num <= 1return false;    // 1은 소수가 아니다.    
        if (num <= 3return true;    // 2와3은 소수이다.
        if (num % 2 ==0return false;
        for(int div = 3; div <= Math.sqrt(num); div+=2) {
            if(num % div == 0return false;
        }
        return true;
    }
}
 
 

 

 소수판별법 구현 - 1 과는 약간 차이가 있지만 핵심은 num - 1 까지가 아닌 √n 까지 반복문을 수행한다는 것이 가장 큰 차이점이다. 또 차이점이라고 하면 단지 2가 아닌 짝수를 먼저 걸러줬다는 점과 다음 반복을 수행 할 때 어차피 홀수인 수로 나눠줄 것이니 div += 2 로 다음 반복을 수행하였다.

 

정리

지금까지 알아본 것은 특정한 수 N이 있을때 그 수가 소수인지 아닌지 판별하는 알고리즘을 알아본것이다. 그 중에서 가장 빠른 방법의 시간복잡도는 앞에서 살펴본것 처럼 O(√n) 이다.  예를 들어 1 ~ 1,000,000 까지 수 중에서 소수가 몇개인지 찾아내는 방법을 강구해보자.

앞서 살펴본 방법으로는 대략 1,000,000 * √1,000,000 이다. $10^{9}$ 약 10초 정도 걸린다.  하지만, 더 빠른 방법이 존재한다. 위와 같이 [ 특정 구간] 에서 소수를 구한다고 하면 에라토스네테스의 체를 이용하는 것이 매우 효과적이다.  이는 다음시간에 알아보자!!

 

 

반응형

'Algorithm' 카테고리의 다른 글

[알고리즘] 에라토스테네스의 체  (0) 2021.09.16
[탐색 알고리즘] lower_bound, upper_bound  (0) 2020.07.18