Eratosthenes算法的筛选器

我做了一些搜索，找不到任何有关此实现的信息与我见过的其他任何信息。Eratosthenes算法的筛选器

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

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

编辑：除了可伸缩性还有其他问题吗？同样再次感谢关于推进主要发现的意见。

来源

2009-12-07 Woot4Moo

可能只是一个错字，但你必须为'（$ 1 ... ）代替第三行中的（$ i ...）' – 2009-12-07 17:45:56

这个代码输出的第一个非素数是221. 221是13 * 17。 – Greg 2009-12-07 17:49:28

Damnit。我的意思是169（13 * 13）。 – Greg 2009-12-07 17:51:45

这个问题的主要缺陷是不能缩放。一旦数字足够大，将返回任何东西。模数排除列表需要与搜索一起增长。

来源

2009-12-07 17:42:52 cjk

从我看到的这也是这个算法的一个主要陷阱。我听说10^9是这个算法的真正突破点。 – Woot4Moo 2009-12-07 17:48:00

你的版本在约10^2时失败:) – 2009-12-07 18:03:33

@Peter：实际上，因为7是已知最大的素数，他*筛选*反对，所以不能保证超过49。 @ Woot4Moo：这是你在练习时所做的事情，因为如果你需要一个完整的解决方案，你还有很长的路要走。我自己写了一个主要的发现者jsut来测试CPU的运行速度和多线程，而不是使用SOE，我只是做了数字运算检查任何缺少余数除以3 + = 2 ... – cjk 2009-12-07 21:06:44

它局限于素数高达11扩展它的任何进一步需要添加|| $u % 11 == 0 || $i % 13 == 0 ...等

来源

2009-12-07 17:43:02 eduffy

我的想法是因为任何2,3,5或7可以不是总数的整数我不需要做％11或％13.因为使用整数乘法我不必担心。有没有什么特定的情况可以使2个数字相乘，而这些数字不会使得这个陈述的结果为真？ – Woot4Moo 2009-12-07 17:46:44

我不确定你的意思，但我认为一个反例是121，它是11 * 11，不能被2,3,5或7整除。你需要检查每个小于平方根的素数的一个数字，以确定它是否为素数。 – StrixVaria 2009-12-07 17:51:17

@ Woot4Moo - 你是对的，任何能被2,3,5或7整除的东西都不是素数，但相反是不正确的。格雷格对你的问题的评论有221这样的例子，它不能被这些中的任何一个整除，但也不是主要的。 – cjk 2009-12-07 17:53:28

您可以参考Sieve of Eratosthenes维基百科;和一个PHP实现的this link。

来源

2009-12-07 18:02:58

首先，你只是检查三个数字（3,7和11）。对于Erathosthenes筛，您应该从数字列表开始，2..i。然后循环访问该列表，并删除作为您正在迭代的数字的因素的数字。例如，一旦你达到7，这是首要的，你需要删除49,56和其他7的倍数。

其次，我刚刚描述的方法会缩小非常糟糕 - 如果您尝试寻找素数从1..10^9，你的列表中需要10^9的值。还有除了Erathosthenes的筛其他方式找到素数 - 见http://en.wikipedia.org/wiki/Prime_number

来源

2009-12-07 18:12:51

如果你正在寻找从1到10的质数，你需要很多数字，但少于10 ......但它会成千上万。 – 2009-12-07 18:16:35

好点。我应该补充说：“在这个天真的实现中，...” – 2009-12-07 18:28:00

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

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; 
}

来源

2015-10-07 15:26:10

不错，但问题要求提供有关陷阱，可伸缩性等信息，而不是另一个实现。 – buffjape 2015-10-07 15:34:36

Eratosthenes算法的筛选器

回答

相关问题