Sieve of Eratosthenes implementation is running slowly

Question

I have written this code to find prime numbers, and it works well, but the calculation speeds are incredibly slow. Am I doing this wrong? I know that I might be really doing this the wrong way, but please help me!

using System;
using System.Collections.Generic;

namespace Primenumbers
{
class MainClass
{
    public static void Main (string[] args)
    {

        List<int> NoPrime = new List<int>();

        for(int x = 2; x < 10000;x++)
        {
            for(int y = x * 2;y < 10000;y = y + x)
            {

            if(!NoPrime.Contains(y))
                {
                    NoPrime.Add(y);
                }

            }

        }

        for(int z = 2; z < 10000;z++)
        {
            if(!NoPrime.Contains(z))
            {
                Console.WriteLine(z);
            }
        }


    }
}
}

Answer 1

There is some room for improvement in your code, and I will try to explain that in several steps. But please note that I am not a C# person, so my review refers only to the algorithm and performance itself and not to the style or any language specifics. And most probably I am making a lot of C# errors here.

The following tests were done on a MacBook Pro using Mono.

To show the performance improvement gained in each step, I have rewritten your code a bit:

• The prime numbers are not printed because printing many lines also takes time. Instead, only the number of primes is counted.
• The time for the computation is taken and printed with StopWatch.
• Instead of a fixed upper bound (10,000 in your code) the limit is read from the command line arguments. I used an upper bound of 50,000.

So your code is equivalent to this:

using System;
using System.Collections.Generic;
using System.Diagnostics; // (for Stopwatch)

namespace Primenumbers
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            int maxPrime = int.Parse(args[0]);
            Stopwatch stopWatch = Stopwatch.StartNew();
            int numPrimes = sieve(maxPrime);
            stopWatch.Stop();
            Console.WriteLine("{0} primes in the range 2..{1}, time taken: {2}ms", numPrimes, maxPrime, stopWatch.Elapsed.TotalMilliseconds);
        }

        static int sieve(int maxPrime)
        {
            List<int> NoPrime = new List<int>();
            for (int x = 2; x <= maxPrime; x++)
            {
                for (int y = x * 2; y <= maxPrime; y = y + x)
                {
                    if (!NoPrime.Contains(y))
                    {
                        NoPrime.Add(y);
                    }
                }
            }

            int numPrimes = 0;
            for (int z = 2; z <= maxPrime; z++)
            {
                if (!NoPrime.Contains(z))
                {
                    numPrimes++;
                }
            }
            return numPrimes;
        }
    }
}

and the output is:

5133 primes in the range 2..50000, time taken: 5744.7922ms

Step 1: Jeroen Vannevel suggested to use HashSet instead of List, and indeed this reduces the runtime considerably:

5133 primes in the range 2..50000, time taken: 17.7239ms

But an array of booleans is much faster because it allows direct access to all elements without any lookup. Note that this does need not much more memory. The number of primes below a number N is approximately N/log(N), so "most" numbers are not primes. For example, for our upper limit of 50,000 we need an array with 50,000 elements instead of a hash set with 44,867 = 50,000-5,133 elements.

With an array of booleans the sieve method would be (thanks to @abligh for suggesting a better variable name):

static int sieve(int maxPrime)
{
    bool[] isComposite = new bool[maxPrime + 1];
    for (int x = 2; x <= maxPrime; x++)
    {
        for (int y = x * 2; y <= maxPrime; y = y + x)
        {
            if (!isComposite[y])
            {
                isComposite[y] = true;
            }
        }
    }

    // Count primes ...
    return numPrimes;
}

and now the output is

5133 primes in the range 2..50000, time taken: 1.1336ms

Step 2: If x in the for (int x = ...) loop has already marked as "not a prime" then all the multiples of x are also not primes, which means that the inner y-loop needs not to be executed at all. On the other hand, the multiples y can simply be marked without checking them before:

static int sieve(int maxPrime)
{
    bool[] isComposite = new bool[maxPrime + 1];
    for (int x = 2; x <= maxPrime; x++)
    {
        if (!isComposite[x])
        {
            for (int y = x * 2; y <= maxPrime; y = y + x)
            {
                isComposite[y] = true;
            }
        }
    }

    // Count primes ...
    return numPrimes;
}

Output:

5133 primes in the range 2..50000, time taken: 0.6805ms

Step 3: If a prime x has been found, all lower primes have already been tested and their multiples marked. Therefore y in the inner loop can start as x * x instead of x * 2. As a consequence, x needs only to run from 2 to sqrt(maxPrime):

static int sieve(int maxPrime)
{
    bool[] isComposite = new bool[maxPrime + 1];
    for (int x = 2; x * x <= maxPrime; x++)
    {
        if (!isComposite[x])
        {
            for (int y = x * x; y <= maxPrime; y = y + x)
            {
                isComposite[y] = true;
            }
        }
    }

    // Count primes ...
    return numPrimes;
}

Output:

5133 primes in the range 2..50000, time taken: 0.4782ms

More improvements are possible, e.g. test only 2 and then every odd number, but I hope this is sufficient for a start.

Finally, here are my measurements for an upper limit of 2,000,000:

• Your method: Don't know, did not wait so long
• Using a hash set: 2601.3797ms
• Using a bool array: 55.2455ms
• After applying "step 2": 19.2888ms
• After applying "step 3": 11.6878ms

Answer 2

You're using a List<T> and executing .Contains() on it. In a list, this will iterate over all the values which ends you up with O(n) time each time the inner loop runs: obviously very slow.

Instead use a HashSet<T> which has O(1) lookup.