PHPで素数を求めるプログラムを実装
Javaで素数を求めるプログラムを実装 - にわとり学生のプログラミング備忘録
今回はPHPで実装を行い、前回と同様100万までの素数を求めた際の
実行速度を計測しました。
実行環境
OS:Windows 7 ProfessionalCPU:Intel Core i7-3770 3.40GHz
PHP:5.6.2
改善前の実装コード
<?php ini_set('memory_limit', '512M'); $N = 1000000; $start_time = microtime(true); // 探索リスト $search = []; for($i=2; $i<=$N; $i++){ $search[] = $i; } // 素数リスト $primes = []; do{ $prime = array_shift($search); $primes[] = $prime; // 素数の倍数をふるい落とす foreach ($search as $key => $value) { if($value % $prime === 0){ unset($search[$key]); } } }while($prime < sqrt($N)); foreach ($search as $prime) { $primes[] = $prime; } foreach ($primes as $prime) { print "$prime\n"; } $end_time = microtime(true); $time = $end_time - $start_time; $time = (int)($time*1000); print "実行時間 : ${time}ms\n";
実行結果(結果の表示有り)
(省略) 999961 999979 999983 実行時間 : 11779ms
実行結果(結果の表示無し)
実行時間 : 7482ms
booleanの配列を利用して改善してみます。
booleanの配列を利用して改善した実装コード
<?php $N = 1000000; $start_time = microtime(true); // 探索リスト $search = array_fill(0, $N, true); // 素数でない場合はfalseにする for($i=2; $i<sqrt($N); $i++){ // 素数の倍数では何もしない if(!$search[$i]){ continue; } // 素数の倍数をふるい落とす for($j=2; $i*$j<=$N; $j++){ $search[$i*$j] = false; } } foreach($search as $key => $value){ if($value){ print "$key\n"; } } $end_time = microtime(true); $time = $end_time - $start_time; $time = (int)($time*1000); print "実行時間 : ${time}ms\n";
実行結果(結果の表示有り)
(省略) 999961 999979 999983 実行時間 : 4913ms
実行結果(結果の表示無し)
実行時間 : 499ms
それでもbooleanによる改善後のコードはJavaの改善前のコードよりも速いのを
見ると、アルゴリズムって大事だなと思います!