2

私は、考えられる最速の素数ジェネレーターを作成するアルゴリズムを練習しています。これは私が最新の作業コードです:

    $p = array();
    function isPrime($i) {
        global $p;
        $s = $i / 2;
        foreach ($p as $n) {
            if ($n >= $s) return true;
            if ($i % $n == 0) return false;
        }
        return true;
    }
    $start = microtime(true);
    for ($i = 3, $k = 20000; $i <= $k; $i += 2) {
        isPrime($i) and $p[] = $i;
    }
    echo(microtime(true) - $start);

しかし、その後、より少ない数をテスト$s = $i / 2;するに最適化できることに気付きました。$s = sqrt($i);私がテストしたとき、コードは失敗し、すべての数値を素数として取得します。基本的に que sqrt は失敗し、常に true を返します。

一体何が起こっているのですか？

4

1 に答える 1

2

理由はこの一言

$s = $i / 2;

$i変数の半分の値を$sこのステートメントに格納します

$s = sqrt($i);

の平方根を格納$iします$s

修正されたコード

$p = array();
function isPrime($i) {
    global $p;
    //$s = $i / 2;
    $s = sqrt($i);
    foreach ($p as $n) {
        if ($n > $s) return true;  // The condition here should be $n > $s not $n >= $s
        if ($i % $n == 0) return false;
    }
    return true;
}
$start = microtime(true);
for ($i = 3, $k = 20000; $i <= $k; $i += 2) {
    isPrime($i) and $p[] = $i;
}
//echo(microtime(true) - $start);
echo "<pre>";
print_r($p);

フィドル

出力

 Array
(
[0] => 3
[1] => 5
[2] => 7
[3] => 11
[4] => 13
[5] => 17
[6] => 19
[7] => 23
[8] => 29
[9] => 31
.......
于 2013-04-24T03:58:18.407 に答える