【PHP】素数の計算

素数計算を高速化する。
こちらの記事を自分なりに備忘録としてまとめました。

1万以下の素数のコード

最初に書いたコード

$start = microtime(true);
play();
$end = microtime(true);
print "\n".'処理時間 = ' . ($end - $start) . '秒'."\n" ;

function play()
{  
    for ($i=max($prime)+1;$i<100000; $i++) {
        if (checkPrime($i)) {
          print $i."\n";
        }
    }
}

function checkPrime($num)
{
    $count=0;
    for ($i=2; $i <$num ; $i++) {
        if ($num%$i==0) {
            return false;
        }
    }
    return true;
}

2つの関数で生成する方法しか思いつかなかった

処理時間

処理時間 = 19.969306945801秒

約20秒かかった。

最初から考えて作り直す

素数は約数が1と自分自身のみ

その数が1と自分自身の2回だけ割り切れたならそれは素数

    for ($i=1; $i <10000 ; $i++) {
      // print $i."\n";
      $yakusuu=0;
        for ($j=1; $j <=$i ; $j++) {
            if ($i%$j==0) {
                $yakusuu++;
            }
        }
        if ($yakusuu==2) {
            print $i."\n";
            // break;
        }
    }

処理時間

処理時間 = 1.4896070957184秒

高速化

素数の約数は1と自分自身のみ

ということは奇数のみをループにかければいい
もちろん2は除く。

    printf('%5d',2);
    for ($i=3; $i <10000 ; $i+=2) {
      // print $i."\n";
      $yakusuu=0;
        for ($j=3; $j <=$i ; $j+=2) {
            if ($i%$j==0) {
                $yakusuu++;
            }
        }
        if ($yakusuu==1) {
            printf('%5d',$i);
            // break;
        }
    }
            print "\n";


## 処理時間

処理時間 = 0.39670991897583秒