system
大橋 俊昭

2016.1.16システム開発 

代表取締役

大橋 俊昭

「どれだけ速く」なるかな!?

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

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

 

ネタは「素数」です!!

 

まずは、素数についての復習ですが、学生時代に「エラトステネスの篩(ふるい)」という方法で「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) 割り切れるかどうかは素数のみでチェックすれば良いのです。

 

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

システム開発サービスはこちら
ページTOPへ