[자바] 소수를 판단하는 근거

 

입력받은 숫자가 소수인지 판단하는 근거는 다음과 같다.

• 숫자 1은 소수가 아니다.
• 약수로 1과 자기 자신의 값만 갖는다. 예를 들어, 숫자 13의 약수는 1과 13이므로 소수이다.

 

위 조건에 맞춰 자바 코드를 작성할 수 있다.

static boolean isPrimeNumber(int num) {
    if (num == 1) {
        return false;
    }

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

 

그러나 위 방법으로 소수를 판단하게 되면 소요 시간이 길다는 단점이 있다. 만약 num이 소수이면서 매우 큰 수라면 반복문 수행 시간이 너무 길어지기 때문에 비효율이 존재한다.

 

반복문 소요 시간을 줄이기 위해 소수를 판단하는 근거를 새로 설정한다.

• 숫자 1은 소수가 아니다.
• 숫자 2는 짝수 중에서 유일하게 소수이다. 
• 숫자 2를 제외한 나머지 짝수는 소수가 아니다.
• 3 ~√n까지의 모든 홀수 중에서 나누어 떨어지는 숫자가 있다면 소수가 아니다.

위 조건 중에서 4번 조건이 소수를 판단하는 핵심 근거이다. 이전 반복문에서는 (2 ~ num-1)까지 모든 숫자를 사용하여 나누어 떨어지는지 확인했기에 소수인지 판단하는 소요 시간이 길어졌다. 

그렇다면 3 ~ √n 사이의 모든 홀수만 탐색하면 되는 이유가 무엇일까? 그 이유는 대칭성 때문이다. 예를 들어, 숫자 81이 소수인지 확인해보자. 숫자 81의 약수는 (1, 3, 9, 27, 81)이고, 3~√81 사이의 모든 홀수는 3, 5, 9이다. 숫자 81의 약수를 이루는 숫자들의 대칭성은 다음과 같다.

• (1, 81) -> 1x81 = 81
• (3, 27) -> 3x27 = 81
• (9, 9) -> 9x9 = 81
• (27, 3) -> 27x3 = 81
• (81, 3) -> 81x3 = 81

(1, 81)과 (81, 1) 그리고 (3, 27)과 (27, 3)은 대칭성을 띄고 있다. 대칭성을 띄는 숫자는 탐색 결과가 동일하기 때문에 한 번만 수행해도 된다. 3~√81 사이의 모든 홀수는 3, 5, 9이다. 이 중에서 숫자 81은 3으로 나누어 떨이지기 때문에 소수가 될 수 없다. 숫자 3의 대칭성을 띄는 27을 선택하였을 때도 동일하다. 

 

결국 대칭성 근거에 따라 소수를 판단할 때 모든 숫자를 탐색할 필요 없이 3~√81 사이의 모든 홀수를 구하고, 이 홀수들도 숫자가 나누어 떨어지는지 확인하면 된다. 

static boolean isPrimeNumber(int num) {
    // 1은 소수가 아니다.
    if (num == 1) {
        return false;
    }

    // 2는 짝수 중에서 유일하게 소수이다.
    if (num == 2) {
        return true;
    }

    // 2를 제외한, 나머지 짝수는 소수가 될 수 없다. (약수로 반드시 2를 갖기 때문)
    if (num % 2 == 0) {
        return false;
    }

    // 3~√n 사이의 모든 홀수 중에서 나누어 떨어지는 홀수가 있다면 소수가 아니다.
    for (int i = 3; i * i <= num; i++) {

        if (num % i == 0) {
            return false;
        }
    }
    return true;
}