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

9 Answers

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.

3

As @LeeDanielCrocker suggested, here is an implementation of the Sieve of Eratosthenes that solves the problem instantaneously:

#include <stdio.h> #include <string.h> #define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0) #define SETBIT(x, i) x[i>>3] |= (1<<(i&7)); #define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF; long long sumPrimes(int n) { char b[n/8+1]; long long i, p; long long s = 0; memset(b, 255, sizeof(b)); for (p=2; p<n; p++) { if (ISBITSET(b,p)) { //printf("%d\n", p); s += p; for (i=p*p; i<n; i+=p) { CLEARBIT(b, i); }}} return s; } int main(void) { printf("%lld\n", sumPrimes(2000000)); return 0; }

At ideone, that returns in thirty milliseconds. The optimized version shown below, which sieves only on odd numbers and handles 2 separately, runs in zero time (less than ten milliseconds) at ideone.

#include <stdio.h> #include <string.h> #define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0) #define SETBIT(x, i) x[i>>3] |= (1<<(i&7)); #define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF; long long sumPrimes(int n) { int m = (n-1) / 2; char b[m/8+1]; int i = 0; int p = 3; long long s = 2; int j; memset(b, 255, sizeof(b)); while (p*p < n) { if (ISBITSET(b,i)) { s += p; j = (p*p - 3) / 2; while (j < m) { CLEARBIT(b, j); j += p; } } i += 1; p += 2; } while (i < m) { if (ISBITSET(b,i)) { s += p; } i += 1; p += 2; } return s; } int main(void) { printf("%lld\n", sumPrimes(2000000)); return 0; }

If you're interested in programming with prime numbers, I modestly recommend this essay at my blog; it describes both algorithms given above, covers all the algorithms you will need to solve the prime-number problems at Project Euler, and includes source code in C and four other languages.

1

Please try this way, fast and simple:

int const MAX = 2000000; int checkPrime(int n){ int range = n; for (int i = 2; i < range; i++){ if (n%i == 0){ return 0; } range = n / i; } return 1; } int solution(){ double sum = 0; for (int i = 2; i < MAX; i++){ if (checkPrime(i) == 1){ sum += i; } } return sum; }
2

You can use the Sieve algorithm as this would be the fastest of all:-

In C++

std::vector<int> generate_primes( int n ) { std::vector<bool>sieve( n, true ) ; for( std::size_t i = 2 ; i < sieve.size() ; ++i ) if( sieve[i] ) for( auto j = i*i ; j < sieve.size() ; j += i ) sieve[j] = false ; std::vector<int> primes ; for( std::size_t i = 2 ; i < sieve.size() ; ++i ) if( sieve[i] ) primes.push_back(i) ; return primes ; }
1
#include<stdio.h> #define MAX 2000001 long long a[MAX],c=0; main() { long long i=0,k,j,p,temp=0; long long inc=0; for(i=0;i<MAX;i++) a[i]=i; for(j=2;j*j<MAX;j++) { temp=j; inc=2*temp; k=((MAX-1)/temp)-1; while(k) { printf("%d",inc); printf("\n"); if(a[inc]!=0) a[inc]=0; inc+=temp; --k; } } for(p=0;p<MAX;p++) { if(a[p]!=0) c=c+a[p]; printf("%lld",a[p]); printf("\n"); } printf(" The sum is : %lld",c-1); } 
 Addition of prime No upto 2 million below is the code. Please let me know if anyone have doubt. <html> <body> <input width="200px"/> <input type="button" onClick="onPress()" value="Check"/> </body> <script> function onPress() { var value= document.getElementById("inp").value; var arr=[2,3,5,7], add=17; for(var divisor=2; divisor<value; divisor++) { var prime= true if(divisor%2==0 || divisor%3==0 || divisor%5==0 || divisor%7==0) { prime=false; } if(prime !=false) { for(var j=0; j<arr.length; j++) { if(divisor%arr[j]==0) { prime=false; } } } if(prime==true) { arr.push(divisor); add+= divisor; } } console.log(add); } </script> </html>
1

Here's my javascript solution:

function sumPrimes(num) { // determine if a number is prime function isPrime(n) { if (n === 2) return true; if (n === 3) return true; if (n % 2 === 0) return false; if (n % 3 === 0) return false; var i = 5; var w = 2; while (i * i <= n) { if (n % i === 0) { return false; } i += w; w = 6 - w; } return true; } // subtract 1 for 'not being prime' in my context var sum = isPrime(num) ? num - 1 : -1; for (var x = 0; x < num; x++) { if (isPrime(x) === true) { sum += x; } } return sum; }

Although this answer is not pitch-perfect, it would take less than 3 seconds to execute. Code in C#.

Step 1- omitted numbers which are divisible by 2,3, 5,7
Step 2 - To check prime number we don't need to divide given number with all the numbers. using square root will reduce the code to half time.

 using System; namespace ProjectEuler { class Program { static void Main(string[] args) { long i, j, sum = 17; bool flag = true; for (i = 2; i < 2000000; i++) { if ((i % 2) != 0 && (i % 3) != 0 && (i % 5) != 0 && (i % 7) != 0) { flag = true; for (j = 2; j <= Math.Sqrt(i); j++) { if (i % j == 0) { flag = false; } } if (flag == true) { sum = sum + i; } } } Console.WriteLine(sum); Console.ReadLine(); } } }

You can check the following code in c:

/*Program to print sum of all prime numbers upto 2000000*/ /*To check whether a number is prime or not it takes n^2 time by brute force but this program is sqrt(n) according to mathematical rules to check prime number efficiently. */ #include<stdio.h> #include<stdlib.h> #include<math.h> #define MAX 2000000 int main() { int i,j; unsigned long int prod=0; int prime; for(i=2;i<=MAX;i++){ prime=1; for(j=2;j<(int)(sqrt(i)+1);j++){ if(i%j==0){ prime=0; break; } } if(prime==1){ prod=prod+i; } } printf("%ld",prod); return 0; }
3