【Java】約数を求める

　ついてなので、「素因数分解」や「素数の試し割り」とあまり変わらない方法で、「約数」も求めてみよう。

　約数は「整数 n の約数あるいは因数、因子とは、n を割り切る整数の総称である」(Wikipedia)となっているが、「素因数分解の要素の掛けあわせパターン」とも考えても良いし、「約数が奇数個のときは平方数になる」などという性質があると覚えておくと、たまに役立つことがあるかも知れない。

●約数のリストを作る（掛けあわせの順）

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

/**<h1>約数のリストを作る</h1>
 * <p>先頭の要素は 1 で、例えば、n = 12 のとき、1, 12, 2, 6, 3, 4 のようになる（1×12, 2×6, 3×4）。</p>
 * @param n ： 約数を作る値
 * @return<b>List<Integer></b> ： 約数のリスト
 */
public static final List<Integer> divisor(final int n) {
    final List<Integer> list = new ArrayList<Integer>();

    for (int i = 1; i * i <= n; i++) {    //√n
        if (n % i == 0) {
            list.add(i);          //a x b
            if (i != n / i) {
                list.add(n / i);  //b x a (逆向き)
            }
        }
    }
    return list;
}


//メインでは...
int n = 12;
List<Integer> div = divisor(n);
for (int v : div) {
    System.out.print(v + " ");
}

1 12 2 6 3 4

　要素の順番は「掛けあわせのペアの順」になっているので、偶数個のとき、先頭から２つずつ取り出して乗算すれば元の値になる。
　つまり、

　n = 12 のとき、
　1×12, 2×6, 3×4（4×3, 6×2, 12×1）

となることを表している。ちなみに n が平方数の場合、例えば、

　n = 64 のとき、
　1 64 2 32 4 16 8
　　↓
　1×64, 2×32, 4×16, 8×8（16×4, 32×2, 64×1）

となり、8 が 8×8 と被るので奇数個になることもわかる。

　また、約数の要素を昇順に並び替えたい場合はソートしても良いが、上記のコードを少し改造して、要素を挿入する位置を常にリストの中心にすれば、ソートしたものと同じになる。以下に例を挙げよう。

●約数のリストを作る（昇順）

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

/**<h1>約数のリストを作る(昇順)</h1>
 * <p>先頭の要素は 1 で、要素は昇順になる。例えば、n = 12 のとき、1, 2, 3, 4, 6, 12 のようになる。</p>
 * @param n ： 約数を作る値
 * @return<b>List<Integer></b> ： 約数のリスト
 */
public static final List<Integer> divisor(final int n) {
    final List<Integer> list = new ArrayList<Integer>();

    int p = 0;    //挿入位置
    for (int i = 1; i * i <= n; i++) {    //√n
        if (n % i == 0) {
            list.add(p++, i);             //常に中心に入れていく
            if (i != n / i) {
                list.add(p, n / i);       //常に中心に入れていく
            }
        }
    }
    return list;
}


//メインでは...
int n = 12;
List<Integer> div = divisor(n);
for (int v : div) {
    System.out.print(v + " ");
}

1 2 3 4 6 12

　戻値が「掛けあわせ順」か「昇順」が良いかは、用途に応じて使い分ける方が良いだろう。この上記の２つの例の場合、単純に要素を追加している「掛けあわせ順」の方がわずかに速いが、それほど大きな差はない。

　実際に数学関連の問題を解くときや、全探索で計算量が間に合わないときなどには、その答えをダンプして、その値を「素因数分解」や「約数」などを利用して分析してみると一定の法則が見えたりすることがある。例えば平方数がある一定の差分（２乗倍など）で出ていれば、二分探索のような手法で解けることもある。数値分析の手軽な方法として、この手のライブラリはいくつか作っておくと、色々役立つこともあるだろう。

（関連記事）
【Java】最大公約数・最小公倍数を求める（ユークリッドの互除法）
【Java】拡張ユークリッドの互除法
【Java】素因数分解をする
【Java】素数判定①（試し割り法）