# The 10,001st Prime

Published on 2011-07-22For the first time, my program gave me the wrong answer for a Project Euler question. This one asks you to find the 10,001st smallest prime number, so I wrote a function that would generate a *n* member list of prime numbers and then return the *n*^{th} member. The function iterated over all odd numbers starting at 5, checked if they were prime, and then added them to the list of primes if they were. The first time I ran the program, it gave me a very high prime, but not the 10,001st. The problem lay in my isPrime() method, which originally read as follows:

private static bool isPrime(int i) { int sqrt = (int)Math.Sqrt(i); for (int j = 2; j < sqrt; j++) if (i % j == 0) return false; return true; }

A few non-primes had sneaked into my list because *sqrt* in the above was not actually the square root of *i*, but the square root of *i* rounded down to the nearest integer. I replaced the less than evaluation with a less than or equal to, and the right answer was delivered to me in an instant.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem7 { class Program { static void Main(string[] args) { long hugePrime = generatePrime(10001); Console.WriteLine("The 10,001st prime is {0}", hugePrime); } private static long generatePrime(int p) { List<long> primes = new List<long>(); primes.Add(2); primes.Add(3); for (int i = 5; primes.Count < p; i += 2) { if (isPrime(i)) { primes.Add(i); } } return primes[p-1]; } private static bool isPrime(int i) { int sqrt = (int)Math.Sqrt(i); for (int j = 2; j <= sqrt; j++) if (i % j == 0) return false; return true; } } }