[Java] 소수 판별하기

1. 소수란?

소수(Prime Number)는 컴퓨터 과학과 수학에서 중요한 개념 중 하나입니다. 소수는 자신과 1 이외의 약수를 가지지 않는 2 이상의 자연수를 의미하며, 암호학, 수론 등 다양한 분야에서 활용됩니다. 그러나, 큰 수에 대해 소수를 판별하는 것은 계산 비용이 많이 들 수 있습니다. 따라서, 소수 판별 알고리즘의 효율성을 높이는 것이 중요합니다.

이번 포스팅에서는 자바를 사용하여 소수를 효과적으로 판별하는 최적화된 알고리즘을 공유합니다. 이 방법은 소수를 빠르고 정확하게 찾을 수 있도록 설계되었으며, 특히 큰 수에 대해 뛰어난 성능을 보입니다.

 

2. 소수 판별 알고리즘 구현

아래는 자바로 구현한 소수 판별 함수입니다. 이 함수는 다양한 최적화 기법을 통해 계산량을 줄이고, 효율적으로 소수를 판별합니다.

public static boolean isPrime(int num) {
    // 1. 1 이하의 숫자는 소수가 아니므로 false 반환
    if (num <= 1) return false;
    
    // 2. 2와 3은 소수이므로 true 반환
    if (num <= 3) return true;

    // 3. 2나 3으로 나누어 떨어지는 경우 소수가 아니므로 false 반환
    if (num % 2 == 0 || num % 3 == 0) return false;

    // 4. 5부터 시작해서, 6의 배수와 그 근처의 숫자들만 검사하여 소수를 확인
    for (int i = 5; i * i <= num; i += 6) {
        // 4-1. i 또는 i + 2가 num의 약수라면 소수가 아니므로 false 반환
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }

    // 5. 위의 조건에 걸리지 않았다면 num은 소수이므로 true 반환
    return true;
}

 

3. 알고리즘 설명

• 기본 조건 처리
  • 입력 값이 1 이하일 경우 소수가 아니므로 false를 반환합니다.
  • 2와 3은 소수이므로 이들에 대해 true를 즉시 반환합니다.
  • 2와 3으로 나누어 떨어지는 수는 소수가 아니므로, false를 반환합니다.
• 효율적인 나눗셈 검사
  • 소수는 6의 배수 근처에 위치한 수들(6n ± 1)에만 존재할 수 있음을 이용합니다. 이로 인해 불필요한 계산을 피하고 효율성을 극대화할 수 있습니다.
• 루프 최적화
  • 루프는 i * i <= num 조건까지 반복하며, 이는 검사 범위를 제곱근 이하로 제한하여 불필요한 계산을 줄입니다. 이를 통해 성능이 크게 향상됩니다.

 

4. 최적화된 소수 판별의 장점

이 알고리즘은 일반적인 소수 판별법보다 더 빠르게 동작하며, 특히 큰 수에 대해 효율적으로 소수를 판별할 수 있습니다. 이 방법은 6n ± 1 형태의 수만 검사하기 때문에, 계산량을 크게 줄일 수 있습니다. 또한, 제곱근 범위까지 검사 범위를 제한함으로써, 소수 판별에 필요한 연산을 최소화합니다.

감사합니다.