Problem 10: Summation of primes

Problem:

Please find the problem here.

Solution:

To find all primes under a certain limit, Sieve of Eratosthenes is great. While the name of it sound foreign, this is probably one of the simplest algorithms for finding primes. The wiki have tons on information about the algorithm and I am not going to repeat it here.

The Devil is in the details! To scale this algorithm up, using the standard collection is going to limit the scalability quite significantly. Notice all you need is a single bit to represent whether a number is crossed out or not, one should use a Bitmap. Fortunately, we have BitArray in the .NET framework we can just use, and avoiding the even numbers altogether can give us a big memory saving. Here is the code for my sieve:

namespace Euler
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Threading.Tasks;

    internal static partial class Program
    {
        public static void Problem010()
        {
            Console.WriteLine(Primes(2000000).Select(t => (long)t).Sum());
        }

        private static IEnumerable<int> Primes(int max)
        {
            if (max >= 2)
            {
                yield return 2;
            }

            // sieve[i] represents 2i + 3; [So sieve[0] = 3, sieve[1] = 5] ...
            BitArray sieve = new BitArray(max / 2);
            int i = 0;
            while (true)
            {
                int num = (2 * i) + 3;
                int current_i = i;
                var indexes = Enumerable.Range(1, (sieve.Length - 1 - current_i) / num).Select(t => (t * num) + current_i).ToList();
                Parallel.ForEach<int>(indexes, delegate(int index) { sieve[index] = true; });
                sieve[i] = false;
                i++;
                while (i < sieve.Length && sieve[i])
                {
                    i++;
                }

                if (i >= sieve.Length)
                {
                    break;
                }
            }

            for (int j = 0; j < sieve.Length; j++)
            {
                if (!sieve[j])
                {
                    int num = (2 * j) + 3;
                    if (num <= max)
                    {
                        yield return num;
                    }
                }
            }
        }
    }
}

Note the use of Parallel.ForEach - that speed the crossing up significantly. A careful reader might notice this code is not cache friendly. Yes, it is not, and a cache friendly version can be found online here. The code is not really meant for blazing fast, but just good enough to get the problem solved.

Answer: 142913828922