[Algorithm] 간단한 소수(Prime Number) 판별 알고리즘

소수(Prime Number)란?

• 1, -1과 자기 자신, 자기 자신의 반수로 밖에 나누어 떨어지지 않는 1이외의 정수, 즉 양의 약수가 2개인 자연수

• 1과 자기 자신으로 밖에 나누어 떨어지지 않고 자기 자신의 곱셈의 역수가 없는 수

1 = 1X1 (O)

2 = 1X2, 2X1 (O)

3 = 1X3, 3X1 (O)

4 = 1X4, 2X2, 4X1 (X: 1과 자기 자신을 제외한 2가 있음.)

5 = 1X5, 5X1 (O)

6= 1X6, 2X3, 3X2, 6X1 (X: 1과 자기 자신을 제외한 2,3이 있음.)

이제 이를 프로그램으로 구현하기 위해 필요한 조건을 알아보겠다.

• 비교를 위한 숫자 n이 주어졌을 때 나누는 수를 1을 제외한 2부터 제공. 즉 2~n까지의 범위 i 를 지정한다.
• 이외의 값으로 나눠진다면 소수가 아니다. 즉 n%i ==0 인 상황
• n=5, i=[2,3,4,5]
  5%2 == 3 (O) / 5%3 == 2 (O) / 5%4 == 1 (O) / 5%5 ==0 (X)
• n=6, i=[2,3,4,5]
  6%2 == 0 (X) / 6%3 == 0 (X) / 6%4 == 2 (O) / 6%5 ==1 (O) / 6%6 == 0 (O)
• 나머지를 구했을 때 i가 n을 지정하여 0이 나오면 안되기 때문에 위의 “2~n까지의 범위 i 를 지정” 의 범위를 “2~n-1까지의 범위 i 를 지정” 로 수정하여여한다.(i<=n → i<n)

주어진 n이 소수인지 확인하는 소스는 아래와 같이 될 것이다.

private static boolean isPrime(int n){
        for(int i = 2; i<n; i++){
            if( n % i == 0 ){
                return false;
            }
        }
        return true;
    }

하지만 이는 가장 원초적인 방법이며, 비효율적인 방법이라 할 수 있다.

주어지는 n의 값에 따라 연산하는 범위가 함께 늘어나며 O(N)의 시간복잡도를 가지게된다.

이를 개선하는 방법으로 절반만 n의 범위를 절반으로 줄이는 방법이 있다.

이게 가능한 이유는 n을 12라는 가정으로 약수를 구한다면

1X12, 2X6, 3X4, 4X3, 6X2, 12X1

와 같이 1X12, 2X6, 3X4 의 요소들이 앞 뒤가 바뀐 4X3, 6X2, 12X1 의 요소가 생기기 때문에 절반만 진행해도 같은 결과를 가져올 수가 있다.

이로 인하여 중간 약수까지만 비교를 진행하면된다.

구현은 비교하는 n을 절반으로 나누는 방법과, 루트(√) 사용하여 계산하는 방법이 있다.

루트를 이용하여 계산하는건 절반으로 나눈 n의 원리를 응용한 것이니 루트로 진행하겠다.

Java에서 루트 값을 계산하기 위해서 사용하는 기본 라이브러리 java.lang.Math.sqrt 를 활용하자.

private static boolean isPrime(int n){        
            for(int i = 2; i<=(int)Math.sqrt(n); i++){
                if( n % i == 0 ){
                    return false;
                }
            }
            return true;
    }

시간 복잡도는 O(√n)가 나올 것이다.

이외에도 Heuristic tests, Probabilistic tests, Fast deterministic tests 등 여러 방법이 있지만 복잡한 관계로 일단 킵 해두기로했다…