When I was solving a problem for Project Euler, it asked me to sum up all the 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.
It leads to incorrect results such as 142913828920 and 142913828917, etc.
Why does it go wrong? Theoretically, it doesn't change the number isPrime() sends to main(), does it?
Considering you changed the sum from 142913828922 to 142913828920, then the difference is 2, which means you're interpreting 2 as not prime. Changing sq to sq+1 should achieve that difference. Changing it to sq+2 would end up making 3 not prime.
((int)sqrt(2))+1 == 2
((int)sqrt(3))+2 == 3
and so on.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments