Project Euler Problem 10 asks a very simple question, again dealing with prime numbers:
Calculate the sum of all the primes below two million.
I am giving here two solutions, using two different approaches:
- The first solution uses trial division to create a sequence of all primes under a certain threshold. It's the easiest method to understand.
- The second solution is a naive implementation of the Sieve of Erathostenes.
I first mark all the numbers as candidate primes; then starting from 2 I mark off all the multiples,
move to the next candidate prime, until only primes are left (you can refer to the Wikipedia article for all the details).
As you can see, this second solution has a more imperative feel to it, using mutable data (a dictionary and a counter). Based on my tests for numbers from 1 to 10 millions, it's at least twice as fast as the trial division method.