標準関数で素数を求める

  • 9
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

エラトステネスの篩 / 標準関数

http://www.php.net/manual/ja/function.gmp-nextprime.php

エラトステネスの篩で素数を求めましたが、普通に標準関数に存在していました。
なんでもありだなPHP。

<?php
    // GMPを使った素数の求め方

    // 初期値
    $max = 1000000;
    $now = 1;
    $prime = '';

    // 素数を求める
    while(($now = gmp_nextprime($now)) < $max){
        $prime .= $now.PHP_EOL;
    }

    // 出力
    echo $prime;
ファイル名 10000件時間(秒) 1000件メモリ(kb) 1000000件時間(秒) 1000000件メモリ(kb)
katsurayama_sosu.php 0.00400043 134.38 1.78117800 1362.41
maeda_sosu.php 0.30502999 991.88 180 seconds exceeded
sosu_sample.php 2.81178141 992.17 180 seconds exceeded
tanaka_sosu.php 0.00449991 248.15 0.99830055 8166.82
NurseAngel ArrayIterator 0.00450063 993.30 0.48954952 84322.09
NurseAngel str_repeat 0.00250053 145.05 0.19101894 2363.26
NurseAngel gmp_nextprime 0.01266773 136.09 0.96109605 1361.86

ということで速度はそれなり、メモリ使用量はずっと少ない、そして見た目が圧倒的に簡単という結果になりました。
どうしても速度をひたすら追求しなければならないんだ、なんて時以外はgmp_nextprime()を使っておけば十分でしょう。
というか速度が必要なら他の言語を使え。