埃式筛法和欧拉筛法的对比
in Notes with 0 comment

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

in Notes with 0 comment

beautiful.jpeg

普通筛法

普通筛法举例,验证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;掉了,这也就是说,当我们的合数进入循环时,其实它已经被之前的数筛选过了,所以当合数进入内层循环时,内层循环只执行了一次,从而减少了时间复杂度。

Responses