ご無沙汰しておりました、プログラマーの大橋です。花粉症からのやっと逃れられました。春は一年で最高の季節、ホントに過ごし易くなりました。。。

今回は「どれだけ速くできるか！？」の続編になります。チューンアップしてどこまで速くできたか！？

前回までの「おさらい」

前回は「1,000,000以下の素数」をチェックしていくにあたり、「一番ベタな方法」でサンプルプログラムを準備しました。開発言語は「Java」です。マシンスペックにも依存しますが、恐ろしく時間がかかる結果でした。

処理時間：119789ミリ秒
結果（取得数）：78498件

早速、チューンアップにチャレンジ！！

チューンアップには「素数」の性質を知る必要がありますが、そこまで難しくならず、シンプルに考えてみると、以下のようなことが分かります。

（その1）1桁の素数（2、3、5、7）は算出する必要はありません。
（その2） 自分自身の半分以下の数でしか割り切ることはできません。
（その3） 割り切れるかどうかは素数のみでチェックすれば良いです。

（その2）については、厳密に言うと「自分自身の平方根」以下の数でしか割り切ることができない ということになりますので、厳密にチューンアップしていくことにします。

こんなプログラムになりました！！

前回からの変更点は微々たるものですが、これでチューンアップは完了です。さて、どのくらい速くなっているか、とても楽しみですね。

public static void main(String[] args) {
	// 初期処理
	long stTime = 0; // 開始ポイント
	long edTime = 0; // 終了ポイント

	boolean primeCk = true; // 判定
	List primeNo = new ArrayList(); // 結果（素数一覧）

	// 開始ポイント設定
	stTime = System.currentTimeMillis();

	// 処理実行（1,000,000以下の素数を取得）
	for (int targetNo = 2; targetNo <= 1000000; targetNo++) {

		// 自分自身以外で割り切れる場合、素数ではない
		primeCk = true;
		if (targetNo != 2 && targetNo != 3 && targetNo != 5 && targetNo != 7) {

			for (int i = 0; primeNo.get(i) < (int) Math.sqrt(targetNo) + 1; i++) {
				if (targetNo % primeNo.get(i) == 0) {
					primeCk = false;
					break;
				}
			}

		}

		// 結果（素数一覧）へ保存
		if (primeCk) {
			primeNo.add(targetNo);
		}
	}

	// 終了ポイント設定
	edTime = System.currentTimeMillis();

	// 結果表示
	System.out.println("処理時間：" + (edTime - stTime) + "ミリ秒");
	System.out.println("結果（取得数）：" + primeNo.toArray().length + "件");
}

さて、結果はいかに！！

処理時間：204ミリ秒
結果（取得数）：78498件

なんと 約600倍 も速くなりました。正直、ビックリですよ。結果は 1秒以下 でした。これであれば、もっとイケルはず、凄腕プログラマーの皆さん、是非チャレンジしてみてください！！＜つづく＞