Dziwna sytuacja w sprawdzaniu numeru pierwszego kodu

Question

Kiedy rozwiązywałem problem związany z projektem Euler, poprosiłem mnie o podsumowanie wszystkich liczb pierwszych poniżej 2 milionów. Tu jest mój kodu:

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

Kod ten prowadzi do prawidłowej odpowiedzi, 142913828922. Ale kiedy zmienić dla pętli w isPrime() do:

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

To prowadzi do błędnych wyników, jak i 142913828920 142913828917, itp.

Dlaczego to się nie zgadza? Teoretycznie nie zmienia numer isPrime() wysyła do main(), prawda?

Answer 1

Zważywszy zmieniłeś sumę od 142913828922 do 142913828920, to różnica jest 2, co oznacza, że ​​jesteś interpretacji 2 jak nie pierwszą. Zmiana sq na powinna osiągnąć tę różnicę. Zmiana na sq+2 może spowodować, że 3 nie zostanie wypełnione.

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

i tak dalej.

Answer 2

jeśli zmienisz pętlę do

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

następnie 2 nie jest już uważana za pierwszą, ponieważ przetestować jeśli 2 % 2 == 0.

Podobny w przypadku większych liczb, które będą dodawane, coraz więcej liczb pierwszych nie będzie wykrywanych jako takie.

Answer 3

Lepiej jest używać

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

Zamiast

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

aby tego uniknąć problemów z funkcji sqrt