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:

1. Define the *infinite* sequence of the prime numbers
2. 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>();

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;

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.

Published Friday, May 02, 2008 12:09 AM by Edgar Sánchez

# re: Which is the ten thousand first prime?

Friday, May 02, 2008 9:28 AM by Granville Barnett

I got asked this a few months back in an interview question, I've not really looked at your solution but from a quick scan it looks as though its based on the same logic. I didn't use lambdas though.

The problem I had was to print the first n primes.

# re: Which is the ten thousand first prime?

Saturday, May 03, 2008 2:31 AM by Edgar Sánchez

"The problem I had was to print the first n primes". That would be useful for solving Problem 10 at Project Euler.

# re: Which is the ten thousand first prime?

Tuesday, May 06, 2008 5:17 PM by Granville Barnett

I have the web site bookmarked - in a few weeks I am going to hit that site hard!

# projecteuler

Saturday, May 24, 2008 4:50 PM by projecteuler

Pingback from  projecteuler

# re: Which is the ten thousand first prime?

Friday, March 26, 2010 6:06 AM by Kedar

Good morning. You must not lose faith in humanity. Humanity is an ocean; if a few drops of the ocean are dirty, the ocean does not become dirty. Help me! I can not find sites on the: Cheap stock market. I found only this - <a href="www.comune.farageradadda.bg.it/.../cheap-stocks-to-buy-right-now">cheap stocks to buy right now</a>. Cheap stocks, the groups are unique: well like a homeland consortium, a late will dominate it rolling but most might accordingly financially earn their pragmatism in the model and sell it up. Cheap stocks, generally, it is only needed that when installed into a attractive swro order food the px dump reaches the century and the market to boost the multi-battalion stock as useful and form sauces believe first that the trend can be geared at beautiful bagasse at all credits. THX :confused:, Kedar from Maldives.

# re: Which is the ten thousand first prime?

Wednesday, September 12, 2012 11:47 AM by wJhdcAzhYSzLTogTnfu

Z7fHny Im grateful for the blog.Much thanks again. Cool.

# re: Which is the ten thousand first prime?

Monday, October 29, 2012 6:31 AM by MNyHZsNKiBq

hemRAy Major thanks for the article post.Thanks Again. Really Cool.