Which is the ten thousand first prime?
Prime numbers have a good deal of practical applications (for example in cryptography) but let's face it, even if they would have none, they would still be the favorite toy of mathematicians. In Problem 7 of Project Euler, we are asked to find the 10001st element of the famous list, my approach was this:
- Define the *infinite* sequence of the prime numbers
- From this sequence, throw away the first 10000 items and then take the first of the remaining
Creating an infinite sequence in C# is easy (since version 2) thanks to IEnumerables and, above all, the yield statement:
1 IEnumerable<int> Primes()
2 {
3 yield return 2;
4
5 var primesSoFar = new List<int>();
6 primesSoFar.Add(2);
7
8 Func<int, bool> IsPrime = n => primesSoFar.TakeWhile(p => p <= (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;
9
10 for (int i = 3; true; i += 2)
11 {
12 if (IsPrime(i))
13 {
14 yield return i;
15 primesSoFar.Add(i);
16 }
17 }
18 }
The yield at line 3 returns the first item of the sequence: the always excepcional 2 (the only even prime). Then at line 5 we create a list where we will be saving the generated primes as we progress in the sequence (this way we will gain speed at the cost of memory). The IsPrime(n) function defined at line 9, proposes a method -pretty crude actually- of verifying whether a number is prime: we take all primes generated so far which are lower or equal than the square root of n, and we look for the first among them that divides n evenly, if such a divisor exists then n is not a prime, that is: if none of the primes already generated is an exact divisor of n then FirstOrDefault() returns a 0, signaling the fact that n is indeed a prime. Finally at line 10 starts the loop that, every time the Prime() invoker asks for an item, it progresses thru 3, 5, 7, 9, 11, 13, ... stopping and returning, thru yield, when it finds a new prime.
With this sequence in our hands, step 2 of my plan is utterly simple:
return Primes().Skip(nth - 1).First();
We take the Primes() sequence, ignore the first nth - 1 (in our case nth = 100001) and then take the first of the remaining. This little code returns the answer in far less than a second.