숫자의 가장 큰 소인수를 구하는 Java 프로그램

다음은 주어진 숫자의 가장 큰 소인수(largest prime factor)를 구하는 Java 코드입니다.

예제

import java.io.*;
import java.util.*;
public class Demo{
    static long maxPrimeFactors( long val){
        long max_prime = -1;
        while (val % 2 == 0) {
            max_prime = 2;
            val >>= 1;
        }
        for (int i = 3; i <= Math.sqrt(val); i += 2){
            while (val % i == 0){
                max_prime = i;
                val = val / i;
            }
        }
        if (val > 2)
        max_prime = val;
        return max_prime;
    }
    public static void main(String[] args){
        int val = 148592;
        System.out.println("The largest prime factor of 148592 is ");
        System.out.println(maxPrimeFactors(val));
        val = 890654;
        System.out.println("The largest prime factor of 890654 is ");
        System.out.println(maxPrimeFactors(val));
    }
}

출력 결과

The largest prime factor of 148592 is
251
The largest prime factor of 890654 is
4591

코드 설명

Demo라는 이름의 클래스에는 하나의 값을 매개변수로 받는 정적(static) 메서드 maxPrimeFactors()가 정의되어 있습니다. 이 메서드의 동작 과정은 다음과 같습니다.

1. 먼저 'while' 조건문을 통해 입력값을 2로 나눈 나머지가 0인지 검사합니다. 나누어 떨어지면 변수 max_prime에 2를 할당하고, 값을 오른쪽으로 1비트 시프트(>>= 1)하여 2로 나눈 효과를 냅니다. 이 과정은 더 이상 2로 나누어 떨어지지 않을 때까지 반복됩니다.
2. 이어서 'for' 반복문이 3부터 입력값의 제곱근까지, 매 반복마다 2씩 증가하며 순회합니다. 홀수만 검사하는 이유는 짝수인 소수가 2뿐이며, 2는 이미 앞 단계에서 모두 처리했기 때문입니다.
3. 내부의 'while' 반복문은 현재 값이 반복 변수 i로 나누어 떨어지는지 확인합니다. 나누어 떨어지면 max_prime에 i를 할당하고, 값을 i로 나눕니다. 하나의 소수로 여러 번 나누어 떨어질 수 있으므로 이 검사 역시 반복적으로 수행됩니다.
4. 모든 반복이 종료된 후 남은 값이 2보다 크다면, 그 값 자체가 소수이면서 곧 가장 큰 소인수이므로 max_prime에 할당합니다.
5. 마지막으로 max_prime을 반환합니다.

main 메서드에서는 정수형 변수 val에 148592와 890654를 차례대로 대입하고, 각각의 값을 인자로 전달하여 maxPrimeFactors() 메서드를 호출합니다. 호출 결과로 얻은 가장 큰 소인수를 화면에 출력합니다.

알고리즘의 핵심 원리

이 알고리즘은 시행 나눗셈(trial division) 방식을 기반으로 합니다. 수를 작은 소수부터 차례로 나누어 소인수분해를 진행하면, 마지막에 남는 가장 큰 인수가 곧 가장 큰 소인수가 됩니다. 또한 반복 범위를 값의 제곱근까지만 제한하기 때문에 모든 후보 수를 일일이 검사하는 방식보다 훨씬 효율적이며, 시간 복잡도는 대략 O(√n) 수준입니다.