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;

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

        List NoPrime = new List();

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

    }
}
}

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 NoPrime = new List();
            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 ar

StackExchange Code Review Q#62139, answer score: 24