Java로 숫자의 약수 최소 합 구하기

주어진 숫자의 약수(인수)들 중 곱이 원래 수와 같아지도록 분해했을 때, 그 합이 최소가 되는 값을 구하는 문제는 소인수분해를 이용하면 간단하게 해결할 수 있습니다. 예를 들어 350은 2 × 5 × 5 × 7로 분해되며, 이때의 합은 2 + 5 + 5 + 7 = 19가 됩니다.

핵심 원리는 다음과 같습니다. 두 개의 인수 a와 b에 대해 a × b ≥ a + b가 성립하는 경우(a, b가 모두 2 이상일 때), 더 작은 단위로 쪼갤수록 합이 줄어듭니다. 따라서 숫자를 가장 작은 단위인 소수까지 완전히 분해한 뒤 그 합을 구하면, 그것이 곧 최소 합이 됩니다.

예제 코드

public class Demo {
    static int minimum_sum(int num){
        int my_sum = 0;
        for (int i = 2; i * i <= num; i++){
            while (num % i == 0){
                my_sum += i;
                num /= i;
            }
        }
        my_sum += num;
        return my_sum;
    }
    public static void main(String[] args){
        int num = 350;
        System.out.println("The minimum sum of factors of the number are ");
        System.out.println(minimum_sum(num));
    }
}

실행 결과

The minimum sum of factors of the number are
19

코드 설명

Demo라는 이름의 클래스에는 정적(static) 메서드인 minimum_sum이 정의되어 있습니다. 이 메서드의 동작 과정은 다음과 같습니다.

먼저 합계를 저장할 변수 my_sum을 0으로 초기화합니다. 이후 i를 2부터 시작하여 i * i가 num보다 작거나 같은 동안 반복하면서, num이 i로 나누어떨어지면 i를 합계에 더하고 num을 i로 나눕니다. 이 과정을 통해 2부터 차례대로 소인수를 찾아내며 분해가 진행됩니다.

반복문이 종료된 후에는 남겨진 num 값을 합계에 더합니다. 이때 남은 값은 1 또는 제곱근 이상의 마지막 소인수입니다. 예를 들어 350의 경우 2, 5, 5가 차례로 더해지고 남은 7이 마지막으로 더해져 총합 19가 반환됩니다.

main 메서드에서는 대상 숫자를 350으로 정의한 뒤, 해당 값을 매개변수로 전달하며 minimum_sum 메서드를 호출합니다. 계산된 결과는 관련 안내 메시지와 함께 콘솔에 출력됩니다.

시간 복잡도

이 알고리즘은 i를 √num까지만 검사하므로 시간 복잡도는 O(√N)입니다. 따라서 비교적 큰 숫자에 대해서도 효율적으로 동작합니다.