用於檢查素數不工作的C++代碼

Question

我在使用此C++代碼時遇到問題。整數num是我想檢查它是否爲素數的一個數字。但是這個程序總是返回false。這可能很簡單，但我找不到任何東西。

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2 
     if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out 
      return false; 
     } else if(i == num){ //if we've already done checks as high as possible and not tripped out yet then report success 
      return true; 
     } 
} 

Answer 1

i == num不會發生，因爲你的循環條件是i<num。嘗試：

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2 
    if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out 
     return false; 
    } else if(i == num-1){ //if we've already done checks as high as possible and not tripped out yet then report success 
     return true; 
    } 
} 

正如下面指出的，這裏的else條件是多餘的，你只需要檢查2至sqrt(num) - 因爲其餘的因素已經得到遏制。

根據您想要解決問題的複雜程度，可以進行更多改進。現實中的大多數方法都使用概率算法。

Answer 2

您不必檢查每個數字，因爲很多數字都可以輕易排除。例如，在檢查num不能被2整除後，您可以跳過所有其他偶數。這爲您節省了一半的測試。

我們也肯定知道任何其他因素必須小於num/2（或者真的是sqrt(num)，但這很難計算）。這些知識可以爲我們節省另外一半的測試。

所以現在我們有：

if (num % 2 == 0) 
    return false; 

for(int i = 3; i < num/2; i += 2){ 
    if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out 
     return false; 
    } 
} 

// arriving here we have found no factors, so it must be a prime 
return true; 

Answer 3

bool CheckPrime(int num) { 
    bool yayornay = true; 
    for(int i = 2; i < num; i++) { 
     if(num % i == 0) { 
      yayornay = false; 
      break; 
     } 
    } 
    return yayornay; 
} 

Answer 4

這裏寫的正確方法你的意思：

int i=2;      // move declaration out 
for(/*int i=2*/;i<num;i++){ 
     if(num % i == 0){ 
      return false; 
     } // else   // and the final test too 
} 
if(i == num){     
    return true; 
} 

但是，這不是有效的。你只需要檢查i的不超過sqrt(num)。另外，如果你檢查num%2，有沒有更多需要檢查其他任何偶數，所以你可以使用的2增量或者你甚至可以通過數：

if(num == 2 || num == 3) return true; 
if(num < 2 || num % 2 == 0 || num % 3 == 0) return false; 
for(int i=5, j=7, lim=sqrt(num); i<=lim; i+=6, j+=6){ 
     if(num % i == 0 || num % j == 0){ 
      return false; 
     } 
} 
return true; 

_{（注意：這是比這裏的另一個答案更有效，它說這是對這個答案的初始版本的「優化」）。}

Answer 5

Will Ness的代碼的一個小的優化，只需計算for的外部sqrt數。條件檢查執行很多次，並且沒有意義每次計算sqrt。

if(num == 2) return true; 
if(num < 2 || num % 2 == 0) return false; 
int sqrt = sqrt(num); 

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

到目前爲止，我認爲這是最有效的方法！

Answer 6

bool isprime(int n) 
{ 
    if(n<2) return false; 
    if(n==2)return true; 
    for(int i=2;i<=sqrt(n);i++) 
     if(n%i==0) return false; 
    return true; 
}