## 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:

`#!/usr/bin/python"""Python based code solution to problem 10 of project euler."""import math def is_prime(divided):  divisor = 3  sqrt_divided = int(math.sqrt(divided))  while divisor <= sqrt_divided:    if divided % divisor == 0:      return False     divisor += 2   return True if __name__ == "__main__":  print sum([2] + [x for x in xrange(3,2000000+1, +2) if is_prime(x)])`

And for Haskell the code looks like:

`module Main where prime_wrapper:: Int -> [Int]prime_wrapper divided = prime 3 divided (round . sqrt. fromIntegral \$ divided) prime:: Int -> Int -> Int -> [Int]prime divisor divided sqrt_divided  | divisor > sqrt_divided = [divided]  | mod divided divisor == 0 = []  | otherwise = next_prime  where next_prime = prime (divisor + 2) divided sqrt_divided main :: IO ()main = print \$ sum primes   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

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

`#include <iostream>#include <math.h>#include <string>#include <sstream> using namespace std;int w,x,z,result;int * y;bool isprime;int table[1000000];//only odd numbers can be primeint main (){{table[0]=2;w=1;for (x=3, isprime=true ;x<2000000 ;x++,isprime=true){for (y=&table[0];*y<=sqrt (x), isprime==true; y++){if (x%*y!=0&&*y>sqrt (x)){result=(result+x);cout << x <<",";  //RIGHT HEREtable[w]=x;w++;}else if (x%*y!=0){isprime=true;}else {isprime=false;} }}while (int a=1)cout << result <<",";}		return 0;}`

### 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:

`if (x%*y!=0){  if (*y > sqrt(x)){    #stuff  } else {    isprime = true;  }} else {  isprime=false;}`

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.

`#include <stdio.h>#include <math.h> #define LIMIT 2000000 int bits[LIMIT/8 + 1]; #define GET_BIT(n) ((bits[n/8]>>(n%8))&1)#define SET_BIT(n) (bits[n/8] |= 1 << (n%8)) int main() {  int sqrt_lim = (int)(sqrtf(LIMIT)+1);   long long sum=0;  for (int i=2; i<LIMIT; i++) {    if (! GET_BIT(i)) { // Found a prime/*       printf("%d\n", i); */      sum += i;      if (i<=sqrt_lim) for (int j=i*i; j<LIMIT; j+=i) {	SET_BIT(j);      }    }  }  printf("%lld\n", sum);}`

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.