素数を求めるにはエラトステネスの篩を使います。
理屈的には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");
}
}