Edited at

Javaで素数(エラトステネスの篩)

More than 5 years have passed since last update.

素数を求めるにはエラトステネスの篩を使います。

理屈的にはWikipediaのエラトステネスの篩でも良いですが、

http://www.geisya.or.jp/~mwm48961/math/m3prime2.htm

の方が理解しやすかったです。

今回はコードへ説明を書きました。


分かりやすい版

通常とおり、エラトステネスの篩を使って特定の数値までに存在する

素数の数を求めます。

// 遅くなるのでコメントアウト

を外せば素数の出力も行います。

package aoj;

import java.text.NumberFormat;

public class PrimeNumber {
public static void main(String args[]) {
long startTime = start();
// 0 - 100000までの素数を出力する
int num = 100000;
// 素数判定フラグ
boolean isPrime = false;
// 素数の数をカウント
int count = 2; // 2,3を入れているのでその分カウントとしてからスタート
// 4は素数ではないので計算しない
// i += 2 をすることで偶数は素数計算しない(2以外の偶数は素数ではないため)
for (int i = 5; i <= num; i += 2) {
// 素数判定対象(i)は素数判定対象(j)の平方根以下で除算する
for (int j = 2; j * j <= i; j++) {
// 除算できた場合は素数ではないため判定から抜ける
if (i % j == 0) {
isPrime = false;
break;
}
isPrime = true;
}
if (isPrime) {
count++; // 素数をカウント
// 遅くなるのでコメントアウト
// System.out.println("PrimeNumber -> " + i);
}
}
System.out.println("PrimeNumberCount -> " + count);
end(startTime);
}

private static long start() {
long nanostart = System.nanoTime();
return nanostart;
}

private static void end(long nanostart) {
long nanostop = System.nanoTime();
NumberFormat nanoformat = NumberFormat.getNumberInstance();
nanoformat.setMaximumFractionDigits(3);// 小数点以下の桁を3桁に設定
nanoformat.setMinimumFractionDigits(3);
System.out
.println("処理時間は"
+ nanoformat
.format((double) (nanostop - nanostart) / 1000 / 1000 / 1000)
+ "sec");
}
}


高速版

分かりやすい版でも十分早いのですが、もっと大きな範囲の素数を求める場合、

一桁増やすだけでもかなり速度が落ちます。

この辺りを改善した考え方が以下のコードです。

[引用元]http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_196

package aoj;

import java.text.NumberFormat;

public class PrimeNumberFast {
public static void main(String args[]) {
long startTime = start();
// 0 - 100000までの素数を出力する
int num = 100000;
// 高速バージョン
num = (num - 3) / 2;
int[] primeList = new int[num];
for (int i = 0; i < num; i++) {
primeList[i] = 1; // 1は素数扱いで管理する。(最初は全て素数として管理)
}
System.out.println("PrimeNumber -> " + 2);
int count = 1; // 2の分をカウント
for (int i = 0; i < num; i++) {
// primeList[i] == 0 の場合は素数ではないため演算しない
if (primeList[i] == 1) {
int primeNum = i + i + 3;
// 遅くなるのでコメントアウト
// System.out.println("PrimeNumber -> " + primeNum);
count++;
// 素数と判定した場合、素数を計算対象範囲(num)になるまで
// 足しあげていき、素数ではない数値として判断する
// これを行うことで、例えば、 3, 6, 9, 12 ... num
// の数値に対して余分な演算を行わないようにしている
for (int j = i + primeNum; j < num; j += primeNum) {
primeList[j] = 0;
}
}
}
System.out.println("PrimeNumberCount -> " + count);
end(startTime);
}

private static long start() {
long nanostart = System.nanoTime();
return nanostart;
}

private static void end(long nanostart) {
long nanostop = System.nanoTime();
NumberFormat nanoformat = NumberFormat.getNumberInstance();
nanoformat.setMaximumFractionDigits(3);// 小数点以下の桁を3桁に設定
nanoformat.setMinimumFractionDigits(3);
System.out
.println("処理時間は"
+ nanoformat
.format((double) (nanostop - nanostart) / 1000 / 1000 / 1000)
+ "sec");
}
}