数の約数の最小合計を求めるJavaプログラム

ある整数の約数の最小合計を求めるには、素因数分解を利用するのが効果的です。合成数を素因数に分解すると、その和は必ず元の数以下になるため、素因数ごとに足し合わせた値が最小の合計となります。以下に、この考え方を実装したJavaコードを示します。

サンプルコード

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 クラスには、静的メソッド minimum_sum が定義されています。このメソッドは、まず合計値を格納する変数を0で初期化します。その後、2から順に「i × i が対象の数以下である間」ループを回し、数が i で割り切れる限り、i を合計に加算しながら数を i で割っていくことで素因数分解を行います。

ループ終了後、残った数（1より大きい場合はそれ自体が素因数）を合計に加算し、結果を返します。試し割り法では平方根まで確認すれば十分なため、計算量を抑えられる点もポイントです。

main メソッドでは、対象となる数値として 350 を定義し、それを引数として minimum_sum メソッドを呼び出しています。350 は 2 × 5 × 5 × 7 と素因数分解できるため、最小合計は 2 + 5 + 5 + 7 = 19 となり、その結果がメッセージとともにコンソールに出力されます。