This solution uses half the space by simply ignoring all even numbers. It will require a little index calculation. Also, primes are generated one by one instead of returning a list.
Another optimization can be made by starting the crossing out of multiples of a prime p at p2. Any smaller number will already have been crossed out. For the same reason, we can stop looking for non-primes at Sqrt(bound)
. (Any number greater than that will have been crossed out as a multiple of a smaller number.)
public static IEnumerable<int> Primes(int bound)
{
if (bound < 2) yield break;
yield return 2;
BitArray notPrime = new BitArray((bound - 1) >> 1);
int limit = ((int)(Math.Sqrt(bound)) - 1) >> 1;
for (int i = 0; i < limit; i++) {
if (notPrime[i]) continue;
int prime = 2 * i + 3;
yield return prime;
for (int j = (prime * prime - 2) >> 1; j < notPrime.Count; j += prime) {
notPrime[j] = true;
}
}
for (int i = limit; i < notPrime.Count; i++) {
if (!notPrime[i]) yield return 2 * i + 3;
}
}
Software developer with a bachelor degree and a few years experience (studied computer science at a university as well, but didn't finish). Really love C#, but work usually involves Java. Some experience with VB and C as well.
When hobbying I almost exclusively use C# and AutoHotkey. In a previous life I did some Haskell and Modula-3 and similar stuff. I enjoy games and solving puzzles like on http://projecteuler.net/ (I think I'm stuck at level 4, though)