什麼是更好的方法來檢查一個數字是否爲總數？

可能重複：
Checking if an int is prime more efficiently 什麼是更好的方法來檢查一個數字是否爲總數？

bool isPrime(int num) 
{ 
    for(int i = 2; i <= (num/2)+1; i++) 
    { 
     if(num % i == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
}

我看維基百科上，但我不明白任何它所描述的快速素性測試。

來源

2011-07-18 Avery3R

除了在你的算法下文所述的簡單的錯誤，「精益求精」的方式要複雜得多。數百年來，數學家一直在研究素數。 –

@Kirill：在標記爲複製之前閱讀另一個問題，該問題是關於找到具有某些特徵的素數（即許多數字必須經過測試）。我確實相信這個問題以前曾被問過，但事實並非如此。 –

首先，你只需要迭代，而i * i <= num。

之後，您可能會注意到測試數字是否爲2的倍數僅僅是一個測試。一旦你知道這個數字不是偶數，你就知道沒有偶數因素，所以你可以跳過測試它們。

這導致：

bool isPrime(int num) 
{ 
    if (num < 4) return true; 
    if (~num & 1) return false; 
    for(int i = 3; i * i <= num; i += 2) 
    { 
     if (num % i == 0) return false; 
    } 
    return true; 
}

來源

2011-07-18 04:11:47

你確定'if（〜num＆1）return false;' –

@Martin：很確定。即使不少於四個數字也不是素數。你有沒有失敗的情況？ –

也許你應該加上'if（num <1）返回false;'因爲IIRC，素數在定義上大於1. –

更好的方式（如果你想加快你的應用程序）是預先計算的第一個素數，將它們添加到數組，只是搜索你的號碼中，或者檢查數組元素的劃分。

你也可以檢查num % i == 0不高達num/2，但高達sqrt(num)。

PS：

if(num % i == 0) 
     { 
      return true; 
     }

您必須返回false :)

來源

2011-07-18 04:13:01 Olympian

對於不是你的方法更快的東西，你應該建立使用的埃拉托色尼篩等（生成素數至少就一個素數表作爲你測試的數字）。然後只需使用二進制搜索來查看您的號碼。如果你保留表格，如果你以後需要查找更高的數字，你可以逐漸增加它。

Gogo動態規劃。 :-)

來源

2011-07-18 04:14:07

沒有什麼事情可以做，以加快這：

，而不是從2日開始，做i++的，檢查它是否甚至在第一次開始的，如果不是，就在第3和增量I由兩個：

if (num % 2 == 0) { 
    return false; 
} 
for (int i = 3; i <= sqrt(num); i += 2) { ... }

在該示例中的另一個端頭已經是設置上限到你的電話號碼，而不是num/2的平方根。

還有一件事情需要一點點設置，就是使用prime sieve來快速測試您的號碼是否爲總數。

來源

2011-07-18 04:18:14

我不建議每次迭代都進行'i <= sqrt（num）'測試。相反，將'sqrt（num）'存儲在類型爲'int'（或'long'，或另一個整型）的變量中，並與每次迭代進行比較。 –

如果你的輸入集特別小，那麼你可以在你使用sieve of erathones構建素數然後在該篩上進行素性測試的時候有一個步驟。這是你的算法之後的下一步。

有許多性能調整，你可以更快的素性測試，如跳過2和3的因素等

來源

2011-07-18 04:19:21

米勒 - 拉賓測試實現起來比較簡單，雖然證明這是正確得多難。基本上，你多次運行這個測試;每次你從2到你的號碼之間選擇一個隨機的「見證」號碼，然後運行算法。測試會告訴你，你的號碼肯定是複合的（不是總數），也可能是總數（每次出現錯誤的概率爲1/4），所以如果你用10個隨機證人跑10次測試並得到「可能是最好的「，每次的機會都小於百萬分之一，這個數字實際上是複合數。

維基百科在僞代碼的實現：http://en.wikipedia.org/wiki/Miller-Rabin_test#Algorithm_and_running_time

來源

2011-07-18 04:35:39 duskwuff

什麼是更好的方法來檢查一個數字是否爲總數？

回答

相關問題