尋找素數的快速算法？

首先 - 我在這個論壇中查了很多，我還沒有找到足夠快的東西。我嘗試做一個函數，它返回指定範圍內的素數。例如，我使用Eratosthenes篩來完成此功能（使用C＃）。我也試過阿特金的篩但埃拉托色尼一個運行速度更快（在我的實現）：尋找素數的快速算法？

public static void SetPrimesSieve(int Range) 
    { 
     Primes = new List<uint>(); 
     Primes.Add(2); 
     int Half = (Range - 1) >> 1; 
     BitArray Nums = new BitArray(Half, false); 
     int Sqrt = (int)Math.Sqrt(Range); 
     for (int i = 3, j; i <= Sqrt;) 
     { 
      for (j = ((i * i) >> 1) - 1; j < Half; j += i) 
       Nums[j] = true; 
      do 
       i += 2; 
      while (i <= Sqrt && Nums[(i >> 1) - 1]); 
     } 
     for (int i = 0; i < Half; ++i) 
      if (!Nums[i]) 
       Primes.Add((uint)(i << 1) + 3); 
    }

它運行約兩倍的速度比代碼&算法我發現...... 有應該找到素數更快的方法，你可以幫幫我嗎？

來源

2010-09-27 Ohad

在你在尋找什麼樣的素數？只需介於0和max int之間？範圍又有多寬？ – Gleno 2010-09-27 21:52:00

讓我們來說一下類似億/ 2 – Ohad 2010-09-27 21:56:13

有10萬個素數不到10^9，所以預先計算它們會給你一個200MB的表。實際上它只是儲存篩子（10^9位是125MB，而且你不需要存儲偶數位，所以你可以將它全部放在64MB以下）。 – Gabe 2010-09-27 22:07:28

在四處搜尋有關此主題（對於項目Euler）的算法時，我不記得發現任何更快的東西。如果速度真的是問題，你有沒有想過只是存儲素數，所以你只需要查看它？

編輯：快速谷歌搜索發現this，確認最快的方法將只是頁面結果並根據需要查找它們。

多一個編輯 - 你可以找到更多的信息here，本質上是這個話題的重複。那裏的頂級職位表明，atkin的篩比現在更快，只要在飛行中生成。

來源

2010-09-27 21:57:22 jlv

不，這些不是很快，即使我的代碼更快。我真的看到一些說速度非常快的東西（爲什麼我不相信它......）我會明天檢查它，我必須去。不管怎麼說，還是要謝謝你。（這不是重複其他話題，有慢的答案） – Ohad 2010-09-27 22:27:31

這是一個真棒文章，+1 – 2010-10-28 13:22:38

有算法非常非常快於這個簡單的一個，看到我的回答 – 2010-10-28 20:09:31

幾個意見。

對於速度，預先計算然後從磁盤加載。它超快。我很久以前就在Java中做過。
不要作爲數組存儲，存儲爲奇數的位序列。更有效的內存方式
如果你的速度問題是你想讓這個特定的計算運行得很快（你需要證明爲什麼你不能預先計算並從磁盤加載它），你需要編寫一個更好的Atkin篩。它更快。但只是稍微。
您還沒有表明這些素數的最終用途。我們可能完全錯過了一些東西，因爲你沒有告訴我們這個應用程序。告訴我們一個應用程序的草圖，答案將更好地針對您的情況。
爲什麼地球上你覺得有更快的東西存在？你沒有證明你的預感。這是一個非常困難的問題。（也就是找到更快）

來源

2010-09-28 03:39:23 John

測試的主要是這樣一個孔，那我完全同意jlv ...只需存儲並查找它。事實上，應該有一個全球緩存的全球免費Web服務，它可以提供答案...或者更好，java應該在查找中存儲所有素數到max int;在Docker世界中，應該有一個應用程序的圖像，提供圍繞素數的一系列服務，包括查找。它只需要測試它就可以了，然後在任何你選擇的語言中尋找最高性能的方法。 – Beezer 2016-12-05 23:29:00

你可以做的比，使用Sieve of Atkin更好，但它是相當棘手的執行它快速和正確。維基百科僞代碼的簡單翻譯可能不夠好。

來源

2010-09-28 12:06:54 Landei

是啊，我試圖做阿特金斯篩...我的數組還包含偶數，但我沒有碰它們...它比eroathenes篩慢了1.5倍。（我發現的大部分代碼都是從我的eroa中加倍的）。當然 - 我甚至使用素數屬性，我們說我知道要優化...但它仍然較慢（我的數組中有未使用的字節......這應該不重要）。 – Ohad 2010-09-28 22:48:17

爲什麼不向你展示這個代碼呢？ – Landei 2010-09-29 13:15:42

描述它的文章的作者之一的非常快速的C實現在http://cr.yp.to/primegen.html – Olathe 2010-10-04 01:23:50

到目前爲止，我的經驗中最快的算法是Erathostenes的篩子，其中輪子因子分解爲2,3和5，其餘數字中的素數表示爲字節數組中的位。在我3歲的筆記本電腦的一個核心上的Java中，需要23秒來計算高達10億次的質數。

隨着輪子因數分解，Atkin的篩子減慢了大約兩倍，而使用普通的BitSet時，它快了大約30％。參考this answer。

來源

2010-10-28 12:39:00 starblue

我做了一個算法，可以從範圍2-90 000 000我350M筆記本找到素數爲0.65秒，用C寫的....你必須使用位運算，並擁有「代碼」重新計算指數你的數組的索引你想要的具體位。例如，如果你想數2皺褶，具體位將是例如.... 10101000 ......所以如果你從左邊看......你指數4,6,8 ......完蛋了

來源

2011-03-22 09:50:21 DarkEye

尋找素數的快速算法？

回答

相關問題