# Project Euler #7: 10001st prime

This is my implementation of Project Euler #7. Have I overdone it again? Is there anything else I should or should not do? It runs in 9 milliseconds on my computer.

What is the 10001st prime number?

static int NPrimeGenerator(int nPrime)
{
List<int> primes = new List<int>();

int nPrimeVal = 3;

while (primes.Count != nPrime)
{
int sqrtNPrimeVal = (int) Math.Sqrt(nPrimeVal);

foreach (int i in primes)
{
if (nPrimeVal % i == 0) { break; }

if (i >= sqrtNPrimeVal)
{
break;
}
}

nPrimeVal += 2;
}

return primes[primes.Count - 1];
}

static void Main(string[] args)
{
Stopwatch s = new Stopwatch();
s.Start();

int nPrime = NPrimeGenerator(10001);

s.Stop();

Console.WriteLine(nPrime);

Console.WriteLine(s.ElapsedMilliseconds);
}


Have I overdone it again?

I think it's not bad at all. I don't think you overdid anything.

Is there anything else I should or should not do?

Notice that the condition primes.Count != nPrime of the while loop is unnecessary evaluated many times: when nothing was added to the list, the re-evaluation is pointless.

You could improve this by changing it to an infinite loop with while (true), and moving the original condition to the point right after adding a prime to the list. If the target count is reached, break out of both loops.

TOP: while (true)
{
int sqrtNPrimeVal = (int) Math.Sqrt(nPrimeVal);

foreach (int i in primes)
{
if (nPrimeVal % i == 0) { break; }

if (i >= sqrtNPrimeVal)
{
if (primes.Count == nPrime)
{
break TOP;
}
break;
}
}

nPrimeVal += 2;
}


But I think a bigger problem with this code is the poor naming, especially of variables:

• nPrimeVal implies a prime value, possibly the n-th prime. But that's not the case, making it very misleading. possiblePrime would be better.
• nPrime implies.... I don't really know what. It's the target count, so I'd name it targetCount
• NPrimeGenerator is not a great name. The method returns the n-th prime number, so GetNthPrime would seem more natural

It's good that you skip even numbers when searching for the next time. What would be even better is to use a sieve, a popular choice being the Sieve of Eratosthenes.

Lastly, a little thing, but note that in the condition i >= sqrtNPrimeVal you can drop the equality (making it i > sqrtNPrimeVal), as in the case of equality the condition will not be reached, thanks to the break right before it.

Considering the implementation:

• Everything that has been mentioned by janos.
• Since you are skipping even numbers, checking nPrimeval%2 is redundant.

Optimisation:

• Since primes can be represented as 6x+1 or 6x-1, you could run the roop as afast as three times the current execution by following a simple algorithm.
1. Add 2,3 into primes initially.
2. Start with nPrimeVal as 5 a representation of (6x-1).
3. Run the loop as currently done.
4. Inside the loop check for nPrimeVal (6x-1) and nPrimeVal+2(6x+1) and after the loop increase nPrimeVal by 4.
5. Rest follows the current algorithm. Link: Project Euler Problem #10

Everything is clean and good. Above optimisation is just for information sake :) Do include jason's inputs.