소수의 판별

1. 소수(Prime Number) 란?

1보다 큰 자연수 중에서 자신 보다 작은 두개의 자연수를 곱하여 만들수 없는 자연수 입니다.

 

 

2. 소수(Prime Number)의 예

6 = 2 * 3 으로 6을 만들 수 있기 때문에, 소수(Prime Number)가 아닙니다. 7의 경우에는 1과 7을 제외 하고는 곱하여 7을 만들 수 없기 때문에, 7은 소수(Prime Number) 입니다. 

 

 

3. 소수(Prime Number) 판별 java 소스 코드

public class PrimeNumber {
    public static void main(String[] args) {
        PrimeNumber pn = new PrimeNumber();
        System.out.println(pn.isPrimeNumber(6));
        System.out.println(pn.isPrimeNumber(7));
    }
	
    // 소수 판별
    public boolean isPrimeNumber(int x) {
        for (int i = 2; i < x; i++) {
            if (x % i == 0)
                return true;
        }
        return false;
    }
}

 

출력 결과

 

위 소스 코드 처럼, 2부터 시작해서 소수인지 판별 하고 싶은 숫자 X 까지 나누어 떨어지는지 확인 하므로써, 소수 인지 판별할 수 있습니다. 이는 시간 복잡도 O(X) 가 걸리게 됩니다. 

 

 

4. 효율적인 소수의 판별

정수의 약수가 대칭을 이룬다는 점을 이용해서 소수 판별 알고리즘의 시간 복잡도를 줄일 수 있습니다. 

16의 약수의 경우, 16의 약수(Divisor)는 1, 2, 4, 6, 16 입니다.

1 * 16 = 16

2 * 8  = 16

4 * 4  = 16

8 * 2  = 16

16 * 1 = 16

여기서, 4를 기준으로 서로 (1, 16), (4, 4), (2, 8) 서로 대칭 입니다. 따라서 16이 소수 인지 판별 하기 위해서는 4까지 수가 나누어 떨어지는지 확인 하면 되겠습니다. 여기서 4는 16의 제곱근 입니다. 따라서, 소수 판별을 위해서 제곱근 까지만 확인 하여, 나누어 떨어지는 수가 있는지 확인 하면, 더 빨리 소수 판별을 할 수 있습니다.

 

 

5. 효율적인 소수의 판별 java 소스 코드

public class PrimeNumber {
    public static void main(String[] args) {
        PrimeNumber pn = new PrimeNumber();
        System.out.println(pn.isPrimeNumber2(6));
        System.out.println(pn.isPrimeNumber2(7));
    }

    // 효율적인 소수 판별
    public boolean isPrimeNumber2(int x) {
        final int sqrtNum = (int) Math.sqrt(x);

        for (int i = 2; i <= sqrtNum; i++) {
            if (x % i == 0)
                return false;
        }
        return true;
    }
}

 

출력 결과

 

위 소스 코드는 시간 복잡도가 O(√X) (루트 X) 입니다. 지금 까지는 하나의 수에 대해서 소수인지? 아닌지? 판별 하는 알고리즘 이였습니다. 그렇다면, 전체 수의 대한 범위가 주어졌을 때, 해당 범위 안에서 존재하는 모든 소수를 출력하는 경우에는 더 효율적인 알고리즘이 있습니다. 바로 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘으로 더 빠르게 범위 안의 모든 소수를 찾아낼수 있습니다.

 

에라토스테네스의 체(Sieve of Eratosthenes)