What is the 10001st prime number?

Project Euler problem 7 says:


By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

I believe that my code is working, but very very slowly. I guess the increment divisor can be changed, but I'm not sure how.

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace p7
{
// By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
// What is the 10001st prime number?

class Program
{
// - SET 'divisor' TO 13
// - WHILE( divisor <= ceil[ sqrt(number) ] )
// - IF number%divisor == 0 && number != divisor THEN
// - Not prime / divisible by 'divisor'
// - ELSE IF ceil[ sqrt(number) ] == divisor THEN
// - PRIME!!!
// - ELSE increment divisor by 2
static void Main(string[] args)
{
Stopwatch sw = Stopwatch.StartNew();
int count = 6; // we already know 6 primes: 2,3,5,7,11,13
long x = 14; // so can look for a prime after number 13

while (count < 10001)
{
if (IsPrime(x, 13))
{
count++;
x++;
}
}
Console.WriteLine(x);
Console.WriteLine("Time used (float): {0} ms", sw.Elapsed.TotalMilliseconds);
Console.WriteLine("Time used (rounded): {0} ms", sw.ElapsedMilliseconds);
Console.ReadKey();
}
static bool IsPrime(Int64 p, Int64 divisor)
{
Int64 sqrt = (Int64)Math.Ceiling(Math.Sqrt(p));
while (divisor <= sqrt)
{
if (p % divisor == 0)
return false;
else if (sqrt == divisor)

Your prime testing code is wrong. For example, it would consider 14 to be a prime! You cannot take a shortcut by only testing divisors > 13. Instead:

static bool IsPrime(Int64 p)
{
    if (p % 2 == 0) return false;
    Int64 max = (Int64) Math.Ceiling(Math.Sqrt(p));
    for (Int64 divisor = 3; divisor < max; divisor += 2)
    {
        if (p % divisor == 0) return false;
    }
    return true;
}

Points to note:

• I use a for loop instead of while, as this better expresses what I'm doing.

• I only go up to divisor






• While I do test for p % 2 == 0, this branch will never be taken because we will later modify our prime number search loop to only search odd numbers. I leave that test here for correctness.

• Note also that smaller numbers are more likely to be divisors than larger numbers. It's therefore advantageous to test them early.

Your prime search loop looks at each number in from 13 onward. However with the exception of 2, only odd numbers can be primes. We can therefore halve the search time by incrementing in steps of two.

int count = 6;
int targetCount = 10001;
long x;
for (x = 13 + 2; count < targetCount; x += 2)
{
    if (IsPrime(x)) count++;
}

But wait! If we are finding all prime numbers from 13 onward we can use those to speed up our prime test by only testing appropriate prime factors! We can do this by creating a table of primes:

long[] primes = new long[targetCount];
primes[0] =  2;
primes[1] =  3;
primes[2] =  5;
primes[3] =  7;
primes[4] = 11;
primes[5] = 13;

int counter = 6;
for (long x = primes[counter - 1] + 2; counter < targetCount; x += 2)
{
    if (IsPrime(x, primes)) primes[counter++] = x;
}
// the result is in primes[targetCount - 1]

where IsPrime has been changed to

static bool IsPrime(Int64 p, long[] primes)
{
    Int64 max = (Int64) Math.Ceiling(Math.Sqrt(p));
    foreach (long divisor in primes)
    {
        if (divisor > max) break;
        if (p % divisor == 0) return false;
    }
    return true;
}

And hey presto, is this fast! I get 104743` as an answer in a matter of milliseconds.

How did I make this code so fast?

• Write correct code without taking bad shortcuts.

• Think about what I need and what I have anyway.

• Then, figure out an elegant way to connect those two states. Here, my experience with dynamic programming reminded me to build a table of primes.

StackExchange Code Review Q#40673, answer score: 11