php - 我的 PHP sqrt 练习不起作用

Question

我正在练习创建我能想到的最快的素数生成器的算法。这是我最新的工作代码：

    $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。

到底发生了什么？

Answer 1

原因就是这个说法

$s = $i / 2;

$i将变量的一半值存储在$s此语句中

$s = sqrt($i);

$i存储in 的平方根$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
.......