プログラマーのオーハシです。暖冬だけに凍てつく寒さではないですが、早く暖かくなって欲しいですね。

さて、今回は「どれだけ速くできるか！？」という（勝手に面白いと思っている）企画です。凄腕プログラマーの皆さん、是非チャレンジしてみてください！！

ネタは「素数」です！！

まずは、素数についての復習ですが、学生時代に「エラトステネスの篩（ふるい）」という方法で「100以下の素数」を導き出した経験があると思います。

正式には「正の約数が1と自分自身のみである自然数」ということですが、簡単に言えば「2、3、5、7、9、、、」とかいう「自分自身以外では割り切れない数」と考えて良いでしょう！！

今回は「1,000,000以下の素数」をチェックしていくことにします。件数は一体どのくらい！？ 処理時間はどのくらい！？ それでは、チャレンジスタートします。

早速、プログラムを作ってみましょう！！

まずは、手始めに「一番ベタな方法」でサンプルプログラムを準備しました。開発言語は「Java」です。本当は「C++」が良かったのですが、自分のマシンにはセットアップされていないので「Java」でチャレンジ！！

とてつもなく「基本的なプログラム」になってしまいました。一体どのくらい時間がかかってしまうのか、とても楽しみですよ。

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;
		for (int workNo = 2; workNo < targetNo; workNo++) {
			if (targetNo % workNo == 0) {
				primeCk = false;
				break;
			}
		}

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

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

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

結果は一体どうだったのか！？

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

マシンスペックにも依存しますが、恐ろしく時間がかかってしまいました。結果（取得数）は合っていると思います。

この結果であれば、チョットしたチューンアップで速度向上が期待できますね。「数秒」程度まではイケルはず！！

チューンアップのヒントは！！

（その1）1桁の素数（2、3、5、7）は算出する必要はないですね。
（その2） 偶数は素数ではありません。当然です。
（その3） 1桁目が「0、2、4、5、6、8」であれば素数ではありません。
（その4） 自分自身の半分以下の数でしか割り切ることはできません。
（その5） 割り切れるかどうかは素数のみでチェックすれば良いのです。

サンプルプログラムをカスタマイズしても良いですし、作り直しても構いません。開発言語は問いません。それでは、一体「どれだけ速く」なるのか！？＜つづく＞