LoginSignup
9
8

More than 5 years have passed since last update.

標準関数で素数を求める

Last updated at Posted at 2014-07-14

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

エラトステネスの篩で素数を求めましたが、普通に標準関数に存在していました。
なんでもありだな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()を使っておけば十分でしょう。
というか速度が必要なら他の言語を使え。

9
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
9
8