素数判定

GCJで出たけど、まったく発想すらできなかった。とりあえず基礎からたたき直しの写経だ。

素数は、1ともうひとつだけの約数を持つ整数のこと。整数nの約数は2〜n-1なので、これで割り切れるか試せばよい。

ここでnが約数dを持つとき、n/dもnの約数。n = d * n/d なので√n = √d * √(n/d) ≧ min(d, n/d) なので2〜√nまでの整数をチェックすればよい。

/**
 * 素数かどうか判定する
 */
public static boolean isPrime(int n) {
    // 2〜√nまで試す
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    // 1は素数でない
    return n != 1;
}

/**
 * nの約数を列挙する
 */
public static List<Integer> divisor(int n) {
    List<Integer> res = new ArrayList<Integer>();
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.add(i);
            if (i != n / i) {
                res.add(n / i);
            }
        }
    }
    Collections.sort(res);
    return res;
}

/**
 * 素因数分解
 */
public static List<Integer> primeFactor(int n) {
    List<Integer> res = new ArrayList<Integer>();
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res.add(i);
            n /= i;
        }
    }
    if (n != 1) {
        res.add(n);
    }
    Collections.sort(res);
    return res;
}