約数全列挙

約数を全列挙する方法について、2通り記載しておきます。

① 単純なアルゴリズム

割って0になることを1~Nまで順番に試していきます。

<ソース>

import java.util.ArrayList;
import java.util.List;

/**
 * 約数全列挙
 */
public class yakusu {

    public static void main(String[] args) {

       final int N = 1989;

       List<Integer> yakusu = new ArrayList<Integer>();

       for (int t = 1; t <= N; t++) {
           if (N % t == 0) {
               yakusu.add(t);
           }
       }
       System.out.println(yakusu);
    }
}

<実行結果>

[1, 3, 9, 13, 17, 39, 51, 117, 153, 221, 663, 1989]

②約数の性質を利用して

上記の場合 1989を3で割り切れることが分かれば、1989/3 = 663 と663でも割り切れます。そこで

<ソース>

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 約数全列挙
 */
public class yakusu {

    public static void main(String[] args) {

       final int N = 1989;

       List<Integer> yakusu = new ArrayList<Integer>();

       for (int t = 1; t * t <= N; t++) {
           if (N % t == 0) {
               yakusu.add(t);
               if (t * t != N) {
                   yakusu.add(N / t);
               }
           }
       }
       Collections.sort(yakusu);
       System.out.println(yakusu);
    }
}

こんな風にも書けます。