Return to Revisions

For relatively small numbers, the best method is very likely the Sieve of Erathostenes.

Here's a method I wrote a few years ago that implements it. A useful thing to do is to use a BitArray; it will save a lot of space. It also skips even numbers to save even more space. I also made it return each number in sequence instead of returning a List.

Finding prime numbers up to int.MaxValue takes about 45 seconds (and uses +/- 130Mb of memory). Using 1 million as bound will be lightning fast, though. It can be done faster still, but the code would become more complex.

public static IEnumerable<int> Primes(int bound)
{
    if (bound < 2) yield break;
    //The first prime number is 2
    yield return 2;

    BitArray composite = new BitArray((bound - 1) / 2);
    int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
    for (int i = 0; i < limit; i++) {
        if (composite[i]) continue;
        //The first number not crossed out is prime
        int prime = 2 * i + 3;
        yield return prime;
        //cross out all multiples of this prime, starting at the prime squared
        for (int j = (prime * prime - 2) >> 1; j < composite.Count; j += prime) {
            composite[j] = true;
        }
    }
    //The remaining numbers not crossed out are also prime
    for (int i = limit; i < composite.Count; i++) {
        if (!composite[i]) yield return 2 * i + 3;
    }
}

For larger numbers, you need more advanced techniques. A popular one is the Miller-Rabin primality test.