Sieve of Eratosthenes implementation is running slowly

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;

{
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))
{
}

}

}

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

}
}
}

• Your indentation is off (copy/paste artifact? use spaces, not tabs in SE code blocks ;), and vertical whitespace is inconsistent. You should also consider separating computing from displaying. Sep 6 '14 at 16:43
• Never if in fors if you can avoid it. Aug 4 '16 at 21:00
• If you are unlucky "contains()" could have to loop over all which have previously been added, increasing complexity where you would not have to. Aug 4 '16 at 21:02

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)

{
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))
{
}
}
}

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
• Very interesting answer; I particularly liked the approach of showing the improvements step by step and their effects. It really demonstrates the importance of a good algorithm and the difference a few changes can make. Sep 6 '14 at 23:47
• To avoid !notAPrime perhaps call it bool[] composite. Also, what's wrong with y += x in the inner loop? (not a C# person either) Sep 7 '14 at 18:03
• depending on compiler, actually testing !isComposite[y] in the inner loop can make it run (counterintuitively) faster for some obscure reasons (although that's C-related). added bonus: can count primes while marking, no separate sweep needed. (i.e. start with count = n and decrement on each marking). Sep 30 '14 at 22:06

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.

• Thank you, this solved it, the program now can print the first 2 million prime numbers in under 20 seconds, tyvm! Sep 6 '14 at 17:13