---
title: 素数判定
tags: []
categories: ["Programming", "Algorithm", "PrimeNumber"]
date: 2011-06-07T17:28:04Z
updated: 2011-06-07T17:28:04Z
---

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;
    }