A while back I was working on solving some math problems from the Project Euler site. In order to solve the math problems I needed a Primes Number Sequence Generator. So, I wrote a small class to generate an open ended IEnumerable of Prime Numbers.
The idea is as follows:
- Starting with 2 and 3 as known primes
- For each known prime create an open ended IEnumerable that enumerates over multiples of that prime.
- Find the next prime by advancing each of the Known Primes Multiples Enumerators until the multiple of the prime is greater or equal to the next candidate.
- If one of the Known Primes Multiples Enumerator values is equal to the current candidate, it is not prime.
- If all Known Primes Multiples Enumerators advance past the current candidate, then it is a prime and a new Known Primes Multiples Enumerator is added to the collection.
Because all the IEnumerators are implemented using the yield return mechanism, the enumerations can be open ended, advanced in parallel and be resumed.
So here is the implementation:
public class PrimesIterator
{private static List<KeyValuePair<long, IEnumerator<long>>> knownPrimes;
static PrimesIterator() {knownPrimes = new List<KeyValuePair<long, IEnumerator<long>>>();
AddKnownPrime(knownPrimes, 2);
AddKnownPrime(knownPrimes, 3);
}
public static IEnumerable<long> NewEnumeration(long maxValue)
{ long current = 1;foreach (var knownPrimeStepper in knownPrimes) {
current = knownPrimeStepper.Key;
if (maxValue > 0 && current > maxValue) {yield break;
}
yield return current;
}
for (current = NextPrimeAfter(current); maxValue == 0 || current <= maxValue; current = NextPrimeAfter(current)) {yield return current;
AddKnownPrime(knownPrimes, current);
}
}
private static long NextPrimeAfter(long current)
{while (true) {
current += 2;
double currentRoot = Math.Sqrt(current);foreach (var primeMultiplesStepper in knownPrimes) {
if (primeMultiplesStepper.Key > currentRoot) { return current;}
while (primeMultiplesStepper.Value.Current < current) {primeMultiplesStepper.Value.MoveNext();
}
if (primeMultiplesStepper.Value.Current == current) { // not a prime. Is a multiple of primeMultiplesStepper.Key. break;}
}
}
}
private static void AddKnownPrime(List<KeyValuePair<long, IEnumerator<long>>> knownPrimes, long prime)
{ IEnumerator<long> newPrimeEnumerator = MathHelpers.SteppingItrator(prime).GetEnumerator();newPrimeEnumerator.MoveNext();
knownPrimes.Add(new KeyValuePair<long, IEnumerator<long>>(prime, newPrimeEnumerator));
}
}
And here is a Unit Test that shows usage by extracting the 1000000th Prime Number:
[TestMethod()]
public void NewEnumerationTest()
{ IEnumerable<long> primes = PrimesIterator.NewEnumeration(0);var actual = primes.ElementAt(1000000);
var expected = 15485867L;
Assert.AreEqual(expected, actual);
}
