素數檢查代碼奇怪的情況

Question

當我解決項目歐拉問題時，它要求我總結所有200萬以下的素數。這裏是我的代碼：

#include<stdio.h> 
#include<math.h> 
int isPrime(int); 
int main() { 
    long long int sum = 0; 
    int i; // index 
    for(i = 2 ; i < 2000000 ; i++) { 
     if(isPrime(i)) { 
      sum += i; 
     } 
    } 
    printf("%lli\n", sum); 
} 

int isPrime(int num) { 
    int i; // index 
    int sq = sqrt(num); 
    for(i = 2 ; i <= sq ; i++) { 
     if(num % i == 0) { 
      return 0; 
     } 
    } 
    return 1; 
} 

此代碼導致了正確的答案，142913828922. 但是，當我在isPrime()改變for循環：

for(i = 2; i <= sq+1; i++) // or even sq+2, sq+3, etc. 

這會導致不正確的結果，如142913828920和142913828917等

爲什麼會出錯？理論上，它不會將isPrime()發送到main()，是嗎？

Answer 1

考慮你改變總和從142913828922到142913828920，則差值是2，這意味着你解釋2不素。將sq更改爲sq+1應該實現該差異。將其更改爲sq+2最終會使3不是主要的。

((int)sqrt(2))+1 == 2 
((int)sqrt(3))+2 == 3 

等等。

Answer 2

如果你改變了環路

for(i = 2 ; i <= sq+1 ; i++) 

然後2不再被認爲是首要的，因爲你測試是否2 % 2 == 0。

與您添加的較大數字相似，將不會像這樣檢測到更多和更多的素數。

Answer 3

這是更好地利用相反的

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

for(i = 2 ; i*i <= num ; i++) { 
    if(num % i == 0) { 
     return 0; 
    } 
} 

，以避免與sqrt函數這個問題