Seltsame Situation in Primzahl-Prüfcode

Question

Als ich ein Problem für Project Euler löste, bat es mich, alle Primzahlen unter 2 Millionen zusammenzufassen. Hier ist mein Code:

#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; 
} 

Dieser Code führt zu der richtigen Antwort, 142913828922. Aber wenn ich die for-Schleife ändern in isPrime() zu:

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

Es führt zu falschen Ergebnissen wie 142.913.828.920 und 142913828917 usw.

Warum geht es schief? Theoretisch ändert sich nicht die Nummer isPrime() sendet an main(), oder?

Answer 1

Sie Betrachtet man änderte die Summe 142913828922-142913828920, dann ist die Differenz 2 ist, was bedeutet, du bist 2 als nicht prim zu interpretieren. Das Ändern sq zu sq+1 sollte diesen Unterschied erreichen. Ändern Sie es zu sq+2 würde am Ende machen 3 nicht Prime.

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

und so weiter.

Answer 2

, wenn Sie die Schleife zu

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

dann 2 mehr ändern wird nicht als Primzahl sein, weil Sie, wenn 2 % 2 == 0 testen.

Ähnlich für größere Zahlen, die Sie hinzufügen, mehr und mehr Primzahlen werden nicht als solche erkannt.

Answer 3

Es ist besser,

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

Statt

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

zu verwenden, um diese Probleme zu vermeiden, mit sqrt Funktion