php - 埃拉托色尼筛算法

Question

我进行了一些搜索，但与我见过的所有其他实现相比，我找不到任何关于此实现的信息。

function sieve($top)
{
    for($i = 11; $i<$top; $i+=2)
    {
         if($i % 3 == 0 || $i % 5 == 0 
            ||  $i % 7 == 0)
          {
             continue;
          }
       echo "$i <br />";
   }
}

是的，我知道它只是打印出来，但这不是重要的部分。无论是时间还是其他，主要的陷阱是什么？

编辑：除了可扩展性之外还有其他问题吗？还要再次感谢关于推进主要发现的评论。

Answer 1

这样做的主要缺陷是它无法扩展。一旦数字足够大，任何东西都会返回。您的模数排除器列表需要随着搜索而增长。

Answer 2

你可以参考维基百科上的埃拉托色尼筛法；以及PHP 实现的这个链接。

Answer 3

它仅限于最多 11 的素数。要进一步扩展它，您需要添加|| $u % 11 == 0 || $i % 13 == 0 ...等

Answer 4

首先，您只检查三个数字（3、7 和 11）。对于埃拉托色尼筛，你应该从一个数字列表开始，2..i。然后遍历该列表，并删除作为您正在迭代的数字的因素的数字。例如，一旦达到质数 7，则需要删除 49、56 和其他 7 的倍数。

其次，我刚刚描述的方法的扩展性很差——如果您尝试从 1..10^9 中查找素数，则列表中需要 10^9 个值。除了埃拉托色尼筛之外，还有其他方法可以找到素数 - 请参阅http://en.wikipedia.org/wiki/Prime_number

Answer 5

此功能使用“埃拉托色尼筛法”

function getPrimaryNumbers($n)
{
    $sieve = [];
    for($i = 1; $i <= $n; $i++) {
        $sieve[$i] = $i;
    } 

    $i =2;
    while($i * $i <= $n) {      
        if(isset($sieve[$i])) {
            $k = $i;
            while ($k * $i <= $n) {         
                unset($sieve[$k * $i]);
                $k++;
            }   
        }
    $i++;
    }           
    return $sieve;
}