埃式筛法和欧拉筛法的对比

普通筛法

普通筛法举例，验证n是否为素数，即n恰好可以整除2到n之间的数，若第一次遇到符合条件的，就结束当前循环，验证下一个数。

$t1 = microtime(true);

$n = 50000;
$cnt = 0;
$prime = [];
for ($i = 3; $i <= $n; $i++) {
    for ($j = 2; $j < $i; $j++) {
        if ($i % $j == 0) {
            break;
        }
    }
    if ($i == $j) {
        $prime[$cnt++] = $i;
    }
}

$t2 = microtime(true);
echo 'Time: ', $t2-$t1, PHP_EOL;
echo 'Now memory_get_usage: ', memory_get_usage(), PHP_EOL;

埃式筛法

埃式筛法的基本思想就是，当我们遍历到一个素数时，把所有该素数的倍数（自然是合数）都筛选出来。

$t1 = microtime(true);

$n = 1000000;
$cnt = 0;
$vis = [];
$prime = [];
for ($i = 0; $i < $n; $i++) {
    $vis[] = 0;
}

for ($i = 2; $i <= $n; $i++) {
    if (!$vis[$i]) {
        $prime[$cnt++] = $i;
    }
    for ($j = $i; $j <= $n; $j+=$i) {
        $vis[$j] = 1;
    }
}

$t2 = microtime(true);
echo 'Time: ', $t2-$t1, PHP_EOL;
echo 'Now memory_get_usage: ', memory_get_usage(), PHP_EOL;

该算法筛选2与4的时候，会重复筛选，并没有减少循环次数。

欧拉筛法

首先，我们知道当一个数为素数的时候，它的倍数肯定不是素数。所以我们可以从2开始通过乘积筛掉所有的合数。将所有合数标记，保证不被重复筛除，时间复杂度为O（n）。

$t1 = microtime(true);

$n = 1000000;
$cnt = 0;
$vis = [];
$prime = [];
for ($i = 0; $i < $n; $i++) {
    $vis[] = 0;
}
for ($i = 2; $i < $n; $i++) {
    if (!$vis[$i]) {
        $prime[$cnt++] = $i;
    }
    for ($j =0; $j < $cnt && $i * $prime[$j] <= $n; $j++) {
        $vis[$i * $prime[$j]] = 1;
        if ($i % $prime[$j] == 0) break;
    }
}

$t2 = microtime(true);
echo 'Time: ', $t2-$t1, PHP_EOL;
echo 'Now memory_get_usage: ', memory_get_usage(), PHP_EOL;

我们可以发现，在用埃式筛法的同时，同一个数字也许会被筛选多次。

比如6先被2筛选一次，再被3筛选一次，这样就浪费了很多不必要的时间。

而欧拉筛法通过if ($i%$prime[$j]==0) break;这一步就避免了重复筛选的发生。

我们举个例子，比如：2先筛选了4，然后进行下一个循环，3筛选6和9，

当我们执行到4的时候，可以发现，当i==4时，第一次运行到if ($i%$prime[$j]==0)这一步的时候就直接break掉了。

这也就是说，当我们的合数进入循环时，其实它已经被之前的数筛选过了。

所以当合数进入内层循环时，内层循环只执行了一次，从而减少了时间复杂度。

本文由小小小气鬼创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Oct 22, 2019 07:37 pm