Javaで素数（エラトステネスの篩）

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