方法來計算的無限素數

Question

好吧中，所以也許我不應該SOOO多縮水這個問題......我看到的the most efficient way to find the first 10000 primes職。我在尋找所有可能的方式。目標是爲素質測試提供一站式服務。任何人都知道尋找素數的測試是受歡迎的。

所以：

• 什麼都找到素數的不同方式？

Answer 1

The Sieve of Eratosthenes是一個體面的算法：

1. 取正整數的列表2至任何給定的天花板。
2. 採取的下一個項目中（在第一次迭代2）列表，從列表中刪除它的所有倍數（超出第一）。
3. 重複第二步，直到達到給定的上限。
4. 你的列表現在由純粹的素數。

該算法存在功能限制，因爲它交換內存的速度。當生成非常大的素數列表時，內存容量需要突然增加。

Answer 2

對於一個給定的整數，最快的素性檢查我所知道的是：

1. 取2的列表的整數平方根。
2. 遍歷列表，採取的其餘整數/目前一些

   1. 如果餘數爲任何數量的列表中的零，那麼整數不是素數。
   2. 如果餘數爲非零列表中的所有號碼，那麼整數是素數。

它採用顯著較少的內存比The Sieve of Eratosthenes和普遍較快個人號碼是。使用2列表中的整數根

Answer 3

在你的算法，可以通過只有2個即經過測試奇數提高性能，您只列出需要包含2和所有的奇數3的平方整數的根。這會減少循環次數，而不會引入更多的複雜性。

Answer 4

@theprise

如果我想用一個遞增的循環，而不是一個實例列表（問題內存龐大的數字...），這將是這樣做沒有建立名單的好辦法？

對給定的整數（X％3）進行可分性檢查似乎並不像檢查正常數字（N％X）那樣便宜。

Answer 5

如果你想找到生成素數的方法，這已經在previous question中涵蓋。

Answer 6

@ akdom的問題，對我說：

環流式將正常工作我以前的建議，你不需要做任何的計算，以確定是否一個數是偶數;在循環，直接跳過每個偶數，如下圖所示：

//Assuming theInteger is the number to be tested for primality. 
// Check if theInteger is divisible by 2. If not, run this loop. 
// This loop skips all even numbers. 
for(int i = 3; i < sqrt(theInteger); i + 2) 
{ 
    if(theInteger % i == 0) 
    { 
     //getting here denotes that theInteger is not prime 
     // somehow indicate that some number, i, divides it and break 
     break; 
    } 
} 

Answer 7

羅格斯研究生最近發現了一個recurrence relation that generates primes。它的連續數字的差別會產生素數或1。

a(1) = 7 
a(n) = a(n-1) + gcd(n,a(n-1)). 

這使得很多廢話需要過濾掉。貝努瓦Cloitre也有這種復發，做了類似的任務：

b(1) = 1 
b(n) = b(n-1) + lcm(n,b(n-1)) 

然後連續數的比，減一[B（N）/ B（N-1）-1]爲素數。所有這些的完整說明可以在Recursivity閱讀。

對於篩子，您可以通過使用輪子而不是每次添加一個來獲得更好的效果，請查看Improved Incremental Prime Number Sieves。這是一個車輪的例子。讓我們看看數字，2和5來忽略。他們的輪子是[2,4,2,2]。

Answer 8

某些主要測試僅適用於某些數字，例如，Lucas–Lehmer測試僅適用於梅森數字。

用於大數字的大多數主要測試只能告訴您某個數字是「可能爲素數」（或者，如果數字未通過測試，肯定是而不是素數）。通常情況下，您可以繼續使用算法，直到數字出現質數的概率非常高。

看看this page，特別是它的「另請參見」部分。

Miller-Rabin test是，我認爲，最好的測試之一。在它的標準形式中，它給出了可能的素數 - 儘管已經表明，如果將測試應用於3.4 * 10^14以下的數字，並且它通過了每個參數2,3,5,7,11,13的測試和17，它是，絕對是總理。

AKS test是第一個確定性的，證實的，通用的多項式時間測試。然而，據我所知，最好的實現結果是比其他測試慢，除非輸入是可笑的大。