Lea Lea - 2 months ago 22
C Question

Find the sum of all the primes below two million. Project euler, C

So, everything seems to be working nicely, but the program doesn't give me the correct answer. Mine is 142,915,960,832, whereas it should be 142,913,828,922. The differece is 2,131,910 (if I still can subtract numbers on paper haha) and I have no idea where did I get those two millions. Could anyone help me?

#include <stdio.h>
#include <math.h>

#define BELOW 2000000

int isaprime (int num);

int main (void) {

int i;
float sum = 0;

for (i = 2; i < BELOW; i++) {

if (isaprime(i) == 1) {
sum = sum + i;
printf ("\n%d\t%.1f", i, sum);
}
}

getch();
return 0;
}

int isaprime (int num) {

int i;

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

return 1;
}

Answer

Using float as the sum is the problem. The largest integer k such that all integers from [-k, k] are exactly representable in 32-bit float is 2^241; after that you will start losing precision in some integers. Since your sum is outside that range that, by an absurd margin, you lose precision and all bets are off.

You need to change to a larger type like long (assuming it's 64-bits on your machine). Make the change, and you'll get right answer (as I did with you code):

[ec2-user@ip-10-196-190-10 ~]$ cat -n euler.c
     1  #include <stdio.h>
     2  #include <math.h>
     3  
     4  #define BELOW 2000000
     5  
     6  int isaprime (int num);
     7  
     8  int main (void) {
     9  
    10      int i;
    11      long sum = 0;
    12  
    13      for (i = 2; i < BELOW; i++) {
    14  
    15              if (isaprime(i) == 1) {
    16                      sum = sum + i;
    17              }
    18      }
    19      printf("sum: %ld\n", sum);
    20  
    21      return 0;
    22  }
    23  
    24  int isaprime (int num) {
    25  
    26      int i;
    27  
    28      for (i = 2; i <= sqrt(num); i++) {
    29              if (num % i == 0) {
    30                      return 0;
    31              }
    32              else {
    33                      ;
    34              }
    35      }
    36  
    37      return 1;
    38  }
[ec2-user@ip-10-196-190-10 ~]$ gcc euler.c -lm
[ec2-user@ip-10-196-190-10 ~]$ ./a.out
sum: 142913828922

1: 23 explicit bits in the mantissa plus one hidden bit.