ヽ｜∵｜ゝ(Fantom) の 開発blog？

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

/**<h1>素因数分解のリストを作る</h1>
 * @param n ： 素因数分解する値 (>=0)
 * @return<b>List<Integer></b> ： 素因数分解のリスト
 */
public static final List<Integer> primeFactor(int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {    //n が2以上とわかっていれば、ここは不要
        return list;
    }

    while (n != 1 && n % 2 == 0) {    //2で割り切れるだけ割る
        list.add(2);
        n >>>= 1;        //÷2 の代わり
    }

    for (int i = 3; i * i <= n; i += 2) {    //奇数のみ [O(√n[/2])で可]
        while (n % i == 0) {
            list.add(i);
            n /= i;
        }
    }

    if (n != 1) {
        list.add(n);
    }
    return list;
}


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

import java.util.HashMap;
import java.util.Map;

/**<h1>素因数分解の連想配列を作る</h1>
 * @param n ： 素因数分解する値 (>=0)
 * @return<b>Map<Integer, Integer></b> ： <値, 個数> の連想配列
 */
public static final Map<Integer, Integer> primeFactorMap(int n) {
    final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    if (n < 2) {    //n が2以上とわかっていれば、ここは不要
        return map;
    }

    while (n != 1 && n % 2 == 0) {    //2で割り切れるだけ割る
        if (map.containsKey(2)) {
            map.put(2, map.get(2) + 1);
        } else {
            map.put(2, 1);
        }
        n >>>= 1;        //÷2 の代わり
    }

    for (int i = 3; i * i <= n; i += 2) {    //奇数のみ [O(√n[/2])で可]
        while (n % i == 0) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
            n /= i;
        }
    }

    if (n != 1) {
        map.put(n, 1);
    }
    return map;
}


//メインでは...
int n = 240;
List<Integer> factor = primeFactorMap(n);
for (Map.Entry<Integer, Integer> e : factor.entrySet()) {
    System.out.print(e.getKey() + " = " + e.getValue() + ", ");
}

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

/**<h1>素数のリストを作る（アトキンの篩）</h1>
 * <p>奇数を分類わけし、いくつかの方程式の解での判別と平方数を取り除く篩をかける。</p>
 * @param n ： 取得する素数の最大の値 (>=0) [n を含む]
 * @return<b>List<Integer></b> ： 素数のリスト
 */
public static final List<Integer> primeListAtkin(final int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return list;
    }
    list.add(2);
    if (n == 2) {       //n が3以上とわかっていれば、ここは不要
        return list;
    }

    final boolean[] sieve = new boolean[n + 1];
    final int sqr = (int)Math.sqrt(n);

    int k;
    for (int i = 1; i <= 5; i += 4) {
        for (int y = i; y <= sqr; y += 6) {
            for (int x = 1; x <= sqr && (k = 4 * x * x + y * y) <= n; x++) {
                sieve[k] = !sieve[k];
            }
            for (int x = y + 1; x <= sqr && (k = 3 * x * x - y * y) <= n; x += 2) {
                sieve[k] = !sieve[k];
            }
        }
    }
    for (int i = 2; i <= 4; i += 2) {
        for (int y = i; y <= sqr; y += 6) {
            for (int x = 1; x <= sqr && (k = 3 * x * x + y * y) <= n; x += 2) {
                sieve[k] = !sieve[k];
            }
            for (int x = y + 1; x <= sqr && (k = 3 * x * x - y * y) <= n; x += 2) {
                sieve[k] = !sieve[k];
            }
        }
    }
    for (int i = 1; i <= 2; ++i) {
        for (int y = 3; y <= sqr; y += 6) {
            for (int x = i; x <= sqr && (k = 4 * x * x + y * y) <= n; x += 3) {
                sieve[k] = !sieve[k];
            }
        }
    }
    for (int i = 5; i <= sqr; i += 2) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i * i) {
                sieve[j] = false;
            }
        }
    }
    sieve[2] = sieve[3] = true;

    for (int i = 3; i <= n; i += 2) {
        if (sieve[i]) {
            list.add(i);
        }
    }
    return list;
}


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

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

/**<h1>素数のリストを作る（サンダラムの篩）</h1>
 * <p>整数 n > 1 は、素数または合成数で、合成数だけを篩い落せば素数が残される。</p>
 * @param n ： 取得する素数の最大の値 (>=0) [n を含む]
 * @return<b>List<Integer></b> ： 素数のリスト
 */
public static final List<Integer> primeListSundaram(final int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return list;
    }

    final int h = ((n + 1) >>> 1);    //÷2 の代わり
    final boolean[] sieve = new boolean[h];

    int k;
    for (int i = 1; i * i <= n; i++) {
        for (int j = i; (k = i + j + 2 * i * j) < h; j++) {
            sieve[k] = true;    //k = 4,7,10,12,13,16,17,…
        }
    }

    list.add(2);
    for (int i = 1; i < h; i++) {
        if (!sieve[i]) {
            list.add(2 * i + 1);    //素数の数列
        }
    }
    return list;
}


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

/**<h1>エラトステネスの篩（素数フラグ）を作る</h1>
 * <p>偶数以外で、3 から √n までに対して順番に倍数をふるい落としていく。</p>
 * @param n ： 調べる素数の最大の値 (>=0) [n を含む]
 * @return<b>boolean[]</b> ： 素数である数のインデクスが true となる配列
 */
public static final boolean[] eratosthenesSieve(final int n) {
    final boolean[] sieve = new boolean[n + 1];    //素数フラグ
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return sieve;
    }

    sieve[2] = true;

    for (int i = 3; i <= n; i += 2) {    //2の倍数以外(奇数)を候補にする
        sieve[i] = true;
    }

    for (int i = 3; i * i <= n; i += 2) {    //奇数のみ [O(√n[/2])で可]
        if (sieve[i]) {
            for (int j = i * 2; j <= n; j += i) {    //倍数を候補から除外する
                sieve[j] = false;
            }
        }
    }
    return sieve;
}


//メインでは...
int n = 10;
boolean[] sieve = eratosthenesSieve(n);
for (int i = 0; i < sieve.length; i++) {
    System.out.print(sieve[i] + " ");    //素数である i が true になる
}

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

/**<h1>素数のリストを作る（エラトステネスの篩）</h1>
 * <p>偶数以外で、3 から √n までに対して順番に倍数をふるい落としていく。</p>
 * @param n ： 取得する素数の最大の値 (>=0) [n を含む]
 * @return<b>List<Integer></b> ： 素数のリスト
 */
public static final List<Integer> primeListEratosthenes(final int n) {
    final List<Integer> list = new ArrayList<Integer>();
    if (n < 2) {        //n が2以上とわかっていれば、ここは不要
        return list;
    }

    final boolean[] sieve = new boolean[n + 1];    //素数フラグ
    sieve[2] = true;
    list.add(2);

    for (int i = 3; i <= n; i += 2) {    //2の倍数以外(奇数)を候補にする
        sieve[i] = true;
    }

    //エラトステネスのふるい
    for (int i = 3; i <= n; i += 2) {    //奇数のみ[リスト作成のため O(n[/2])]
        if (sieve[i]) {
            list.add(i);
            for (int j = i * 2; j <= n; j += i) {    //倍数を候補から除外する
                sieve[j] = false;
            }
        }
    }

    return list;
}


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

/**<h1>素数かどうかを判定する（試し割り法）</h1>
 * <p>偶数以外で、3 から √n までに対して順番に割り切れるものが存在しないことをチェックする。</p>
 * @param n ： 調べる値 (n >= 0) [n を含む]
 * @return<b>boolean</b> ： true = 素数 (1 は例外で false)
 */
public static final boolean isPrime(final long n) {
    if (n < 2) {
        return false;
    }
    if (n % 2 == 0) {
        return (n == 2);
    }

    for (long i = 3; i * i <= n; i += 2) {    //奇数のみ [O(√n[/2])で可]
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}


//メインでは...
long n = 46116646144580591L;
System.out.println(isPrime(n));

～(略)～
for (long i = 3; i <= Math.sqrt(n); i += 2) {
    //処理
}
～(略)～

～(略)～
for (long i = 3; i <= n / i; i += 2) {
    //処理
}
～(略)～