# Sum of primes

Published on 2011-07-23The solution to this one (problem 10) took two minutes to write and about the same amount of time to run.

It asks you to find the sum of all primes below 2,000,000, and rather than spend a lot of time writing something new, I copied my implementation of the Sieve of Eratosthenes from problem 3, this time applying it to the set of all integers 2-2,000,000 instead of two through the square root of 600851475143. It's taking a lot longer to run, as the lattermost number is just north of 775,000, and I'm sure the run time of my inefficient sieve increases exponentially relative to any increase in the ceiling provided.

Still no answer after about a minute on my i5. I slightly optimized my set on which to apply the sieve by pre-feeding it the number two and having it only add odd numbers. Halving the initial set should more than halve the processing time required, right? Well, it still wasn't fast enough. Maybe the LINQ `RemoveAll`

method isn't the best way to deal with large sets. So, back to brute force.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem010 { class Program { static void Main(string[] args) { List<int> eratosthenes = new List<int>(); long sum = 2; eratosthenes.Add(2); for (int i = 3; i < 2000000; i += 2) { for (int j = 0; j < eratosthenes.Count(); j++) { if (i % eratosthenes[j] == 0) break; if (eratosthenes[j] > Math.Sqrt(i)) { eratosthenes.Add(i); sum += i; break; } } } Console.WriteLine("The sum of all primes below 2,000,000 is {0}", sum); } } }