Home

Project Euler: Problem 10

Submitted by Bryce on Tue, 07/05/2011 - 20:13

Thank you for your patience as you all (I'm sure) anxiously await my next posting.

Not only has it been a really long time since I posted something technical, it's also been a really long time since I posted a Project Euler solution. On that note, let's go over the challenge:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Seems simple enough doesn't it? Let's find out. For Python the code is:

  1. #!/usr/bin/python
  2. """
  3. Python based code solution to problem 10 of project euler.
  4. """
  5. import math
  6.  
  7. def is_prime(divided):
  8.   divisor = 3
  9.   sqrt_divided = int(math.sqrt(divided))
  10.   while divisor <= sqrt_divided:
  11.     if divided % divisor == 0:
  12.       return False
  13.  
  14.     divisor += 2
  15.  
  16.   return True
  17.  
  18. if __name__ == "__main__":
  19.   print sum([2] + [x for x in xrange(3,2000000+1, +2) if is_prime(x)])

And for Haskell the code looks like:

  1. module Main where
  2.  
  3. prime_wrapper:: Int -> [Int]
  4. prime_wrapper divided = prime 3 divided (round . sqrt. fromIntegral $ divided)
  5.  
  6. prime:: Int -> Int -> Int -> [Int]
  7. prime divisor divided sqrt_divided
  8.   | divisor > sqrt_divided = [divided]
  9.   | mod divided divisor == 0 = []
  10.   | otherwise = next_prime
  11.   where next_prime = prime (divisor + 2) divided sqrt_divided
  12.  
  13. main :: IO ()
  14. main = print $ sum primes 
  15.   where primes = 2 : [ x | x <- [3,5..2000000],  prime_wrapper x /= [] ]

I will be the first to admit that this problem is a little on the easy side. Mostly because you can reuse the code you created for problems 3 and 7, or at least I did. :)

Even though you and I know that Haskell will execute this code faster than Python, I feel I still need to uphold the tradition of posting my highly inaccurate execution times:

Python: 34.054s
Haskell: 20.690s
#1Submitted by Anonymous (not verified) on Mon, 01/30/2012 - 18:31.

Ok people I'm confused, I put

Ok people I'm confused, I put this into c++ and it continously cout x at the point i commented. Like it will say 3,3,3,3,3,3,3,3,3,3,3,3,3 a whole bunch then it will say 5,5,5,5,5,5,5,,5,5,5,5,5,5,5,5,5,5 then 7,7,7,7,7,7,7,7,7,7,7,7, and it slows down the process hugely, anyone know why? Should i just try a different compiler?

Also I'm pretty new to coding any tips on how i could make it better besides the fact that i made the array 1 million which is a waste of memory and i could probably find a better way to do it.

  1. #include <iostream>
  2. #include <math.h>
  3. #include <string>
  4. #include <sstream>
  5.  
  6. using namespace std;
  7. int w,x,z,result;
  8. int * y;
  9. bool isprime;
  10. int table[1000000];//only odd numbers can be prime
  11. int main (){
  12. {
  13. table[0]=2;
  14. w=1;
  15. for (x=3, isprime=true ;x<2000000 ;x++,isprime=true){
  16. for (y=&table[0];*y<=sqrt (x), isprime==true; y++){
  17. if (x%*y!=0&&*y>sqrt (x)){
  18. result=(result+x);
  19. cout << x <<",";  //RIGHT HERE
  20. table[w]=x;
  21. w++;
  22. }
  23. else if (x%*y!=0)
  24. {isprime=true;}
  25. else {
  26. isprime=false;
  27. }
  28.  
  29. }
  30. }
  31. while (int a=1)
  32. cout << result <<",";
  33. }		
  34. return 0;
  35. }
#2Submitted by Bryce on Thu, 02/02/2012 - 14:30.

It's been a really long time

It's been a really long time since I've looked at C code. Because of that I can't suggest much at this moment, I will have to get back to you.

One thing I can suggest that might give you a slight speed up is that in your main loop you're copmaring x%*y!=0 twice. First on line 17 then again for 23. I would change it to something like:

  1. if (x%*y!=0){
  2.   if (*y > sqrt(x)){
  3.     #stuff
  4.   } else {
  5.     isprime = true;
  6.   }
  7. } else {
  8.   isprime=false;
  9. }

Sorry I can't help you more imediately, hopefully I will have more for you in the near future.
#3Submitted by Mandark (not verified) on Fri, 07/08/2011 - 07:11.

Less code less time...

My solution :
print sum(prime_sieve(2000000))

Runs under a second ... Find or write a simple implementation of prime_sieve :-)
#4Submitted by Anonymous (not verified) on Wed, 07/06/2011 - 16:40.

Eratosthenes

That's a horrible solution :). Try this:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#5Submitted by agf (not verified) on Wed, 07/06/2011 - 02:12.

Less primality checking

Try storing the primes you find, then dividing only by them when looking for larger primes, instead of dividing by every number less than the square root.
#6Submitted by Bryce on Wed, 07/06/2011 - 08:48.

Thank you for that

Thank you for that recommendation. I will implement that suggestion soon.
#7Submitted by Erik Sørensen (not verified) on Thu, 08/11/2011 - 03:03.

Solution with Erasthones', in C

Not too difficult... my only bug was overflow in the (i*i) calculation.

  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. #define LIMIT 2000000
  5.  
  6. int bits[LIMIT/8 + 1];
  7.  
  8. #define GET_BIT(n) ((bits[n/8]>>(n%8))&1)
  9. #define SET_BIT(n) (bits[n/8] |= 1 << (n%8))
  10.  
  11. int main() {
  12.   int sqrt_lim = (int)(sqrtf(LIMIT)+1);
  13.  
  14.   long long sum=0;
  15.   for (int i=2; i<LIMIT; i++) {
  16.     if (! GET_BIT(i)) { // Found a prime
  17. /*       printf("%d\n", i); */
  18.       sum += i;
  19.       if (i<=sqrt_lim) for (int j=i*i; j<LIMIT; j+=i) {
  20. 	SET_BIT(j);
  21.       }
  22.     }
  23.   }
  24.   printf("%lld\n", sum);
  25. }

This approach is a couple of orders of magnitude faster (nearly three, in fact):

$ gcc euler10.c -std=c99 -ggdb -lm -O2
$ time ./a.out
142913828922

real 0m0.043s
user 0m0.040s
sys 0m0.000s
#8Submitted by Bryce on Thu, 08/11/2011 - 09:20.

I have to agree Erik, that is

I have to agree Erik, that is really fast. Very Impressive.

Once I fix the versions to use the Sieve of Erasthones, I'm sure I'll get better times. Something I will try and do soon. :)
#9Submitted by Thomas Waldmann (not verified) on Wed, 07/06/2011 - 01:33.

PyPy is fast

PyPy has nice performance for this:

$ time pypy pp.py
142913828922

real 0m5.271s
user 0m5.168s
sys 0m0.088s

CPython 2.7.1:

$ time python pp.py
142913828922

real 0m40.004s
user 0m39.918s
sys 0m0.024s
#10Submitted by Bryce on Wed, 07/06/2011 - 08:48.

That is a damn fast

That is a damn fast improvement. I'm going to have to give PyPy a look. Thanks for sharing your numbers.

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share