Project Euler: Problem 10

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

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. }

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.

Less code less time...

My solution :
print sum(prime_sieve(2000000))

Runs under a second ... Find or write a simple implementation of prime_sieve :-)

Eratosthenes

That's a horrible solution :). Try this:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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.

Thank you for that

Thank you for that recommendation. I will implement that suggestion soon.

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

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. :)

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

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