Situazione strana nel codice di controllo numero primo

Question

Quando stavo risolvendo un problema per Project Euler, mi chiedeva di riassumere tutti i numeri primi sotto 2 milioni. Qui è il mio codice:

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

Questo codice porta alla risposta corretta, 142913828922. Ma quando cambio il ciclo for in isPrime() a:

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

Essa conduce a risultati non corretti, come 142.913.828.920 e 142913828917, ecc.

Perché non funziona? In teoria, non cambia il numero isPrime() invia a main(), vero?

Answer 1

si Considerando cambiato la somma 142913828922-142913828920, allora la differenza è 2, che significa che stai interpretando 2 non primo. Cambiare sq a sq+1 dovrebbe raggiungere tale differenza. La modifica a sq+2 finirebbe per rendere 3 non primo.

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

e così via.

Answer 2

se si modifica il ciclo per

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

poi 2 non è più considerato come il primo, perché si prova, se 2 % 2 == 0.

Simile per i numeri più grandi che si aggiungono, sempre più numeri primi non verranno rilevati come tali.

Answer 3

E 'meglio usare

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

Invece di

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

per evitare questi problemi con la funzione sqrt