Strange situation in the code for checking the number

Question

When I solved the problem for Project Euler, he asked me to bring all primes below 2 million. Here is my 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; } 

This code leads to the correct answer, 142913828922. But when I change the for loop in isPrime() to:

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

This leads to incorrect results, such as 142913828920 and 142913828917, etc.

Why is everything going wrong? Theoretically, it does not change the number isPrime() sends to main() , right?

Answer 1

Given that you changed the amount from 142913828922 to 142913828920 , then the difference is 2 , which means that you interpret 2 as not simple. Changing sq to sq+1 should achieve this difference. Changing it to sq+2 will make 3 not easy.

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

etc.

Answer 2

if you change the loop to

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

then 2 is no longer considered simple because you check if 2 % 2 == 0 .

Similarly, for the large numbers you add, more and more prime numbers will not be detected as such.

Answer 3

Better to use

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

Instead

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

to avoid these problems with the sqrt function