找到10001質數時出錯

我目前正在嘗試解決項目歐拉問題之一，找到10001素數。雖然我的代碼沒有返回正確的數字，甚至當我更改'count'的起始值時返回了一個偶數。下面是我的代碼，如果任何人都可以幫助我這個，它將不勝感激。找到10001質數時出錯

#include <math.h> 
#include <iostream> 
#include <stdbool.h> 
using namespace std; 

bool isPrime(int num); 

int main() 
{ 
    int num = 0, count = 0; 
    while(count < 10001) 
    { 
     num++; 
     while(isPrime(num) != true) 
     { 
       num++; 
       cout << "\n num: " << num; 
     } 
     count++; 
     isPrime(12); 
    } 
    cout << "the 10001's prime number is: " << num << "\n " << count; 
    system("pause"); 
    return 0; 
} 


bool isPrime(int num) 
{ 
     bool checkPrime = false; 
     if(num%2 != 0) 
     { 
       for(int i = 3; i <= sqrt(num); i++) 
       { 
         if(num%i != 0) 
         { 
           checkPrime = true; 
         } 
         else 
         { 
          checkPrime = false; 
          break; 
         }  
       } 
     } 
     else 
     { 
      return false; 
     } 
     if(checkPrime) 
     { 
       return true;  
     } 
     else 
     { 
      return false;  
     }  
}

來源

2013-09-30 Calibre

請用'return checkPrime;'替換最後一條if語句。並且不要重複計算'sqrt（num）'，這是一個昂貴的操作。只需計算一次並存儲結果。 'isPrime（num）！= true'可以被'！isPrime（num）'替代。 – Dukeling

使用標準[Eratosthenes sieve]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）來實現它將會更簡單和更快：它只需要150000字節（可以壓縮成比特或19KB） – mvp

@AlexandruBarbarosie [10000的素數是104729]（http://primes.utm.edu/lists/small/10000.txt），所以我希望如此。 – Dukeling

您在isPrime中的邏輯錯誤。例如isPrime（3）返回false。基本的問題是，您將checkPrime初始化爲false而不是true，這樣任何不進入for循環的小數字都會返回false，即使它是素數。

這是一個（希望）正確的版本，也有一些Dukeling建議的更改。

bool isPrime(int num) 
{ 
    if (num < 2) // numbers less than 2 are a special case 
     return false; 
    bool checkPrime = true; // change here 
    int limit = sqrt(num); 
    for (int i = 2; i <= limit; i++) 
    { 
     if (num%i == 0) 
     { 
      checkPrime = false; 
      break; 
     }  
    } 
    return checkPrime; 
}

來源

2013-09-30 10:36:45 john

非常感謝你，約翰，這現在返回正確的答案。我真的需要學習編寫更少的代碼haha – Calibre

@WillGolledge通常簡單的代碼也是正確的代碼。 – john

你不需要檢查每個數字，看看它是否是一個因素，只是以前找到的素數列表。 –

找到10001質數時出錯

回答

相關問題