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算法的篩選器

回答

相關問題