PHPで素数を求めるプログラムを実装

前回、Javaで素数を求めるプログラムを実装しました。

Javaで素数を求めるプログラムを実装 - にわとり学生のプログラミング備忘録

今回はPHPで実装を行い、前回と同様100万までの素数を求めた際の
実行速度を計測しました。

実行環境

OS：Windows 7 Professional
CPU：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

やはりPHPは、Javaと比べると遅くなってしまいますね。

それでもbooleanによる改善後のコードはJavaの改善前のコードよりも速いのを
見ると、アルゴリズムって大事だなと思います！