# Project Euler: Find 10.001st prime

I have just started learning C# and decided to do some problems from Project Euler. I wrote a code to find 10 001st prime and I thought it would be cool optimize it to make it as fast as possible. How could I improve this to make it even faster?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace primes
{
class Program
{
static void Main(string[] args)
{
long prime = 2;
long largestprime = 2;
long potentialprime = 3;
Console.WriteLine("Enter the prime you want to find: ");
long[] primearray = new long[primenum + 1];
primearray[1] = 2;
Stopwatch sw = new Stopwatch();
sw.Start();
{
bool isprime = true;
for (long x = 1; x < prime; x += 3)
{
if (primearray[x] * primearray[x] > potentialprime)
break;
if (prime > 3 && (potentialprime % primearray[x] == 0 || potentialprime % primearray[x+1] == 0 || potentialprime % primearray[x+2] == 0))
isprime = false;
if (prime <= 3 && potentialprime % primearray[x] == 0)
isprime = false;

}
if (isprime)
{
primearray[prime] = potentialprime;
prime += 1;
largestprime = potentialprime;
}
potentialprime += 2;
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + "ms to find ");
Console.WriteLine(largestprime);
}
}
}

• You might want to take a look at the answers of my question. Commented Jul 18, 2018 at 8:06
• Shouldn't this code calculate the 10.001st prime? I don't think it does. Commented Jul 18, 2018 at 11:03
• I changed it so it can calculate nth number prime where n is taken as an input Commented Jul 18, 2018 at 11:28
• I would focus on increasing readability, maybe you will then spot the answer to your question by yourself. Commented Jul 19, 2018 at 7:16
• This is Project Euler Problem 7 for those who want the link. Commented Jul 29, 2018 at 12:19

As mentioned in the comments, you should go for more readable code:

1) Split by responsibility:

One method for user input:

ulong GetPrimeIndex() { // TODO: Get User input from Console }


The algorithm itself:

ulong FindNthPrime(ulong n) { // TODO: the algorithm }


print the result...

public static void Main(string[] args)
{
ulong primeIndex = GetPrimeIndex();

Stopwatch watch = Stopwatch.StartNew();
ulong nthPrime = FindNthPrime(primeIndex);
watch.Stop();

Console.WriteLine($"{primeIndex} prime is: {nthPrime}"); Console.WriteLine($"Elapsed time: {watch.ElapsedMilliseconds}");
}


2) Naming:

In C# local variable names use camelCase: largestprime should be largestPrime

Because primes are always positive, you should use ulong instead of long. It will give you a broader range to operate in.

I think you're missing a couple of breaks in these tests:

                if (primearray[x] * primearray[x] > potentialprime)
break;
if (prime > 3 && (potentialprime % primearray[x] == 0 || potentialprime % primearray[x+1] == 0 || potentialprime % primearray[x+2] == 0))
isprime = false;
if (prime <= 3 && potentialprime % primearray[x] == 0)
isprime = false;


It should be:

  if (primearray[x] * primearray[x] > potentialprime)
break;
if (prime > 3 && (potentialprime % primearray[x] == 0 || potentialprime % primearray[x + 1] == 0 || potentialprime % primearray[x + 2] == 0))
{
isprime = false;
break;
}
if (prime <= 3 && potentialprime % primearray[x] == 0)
{
isprime = false;
break;
}


Be aware that

primearray[x] * primearray[x]

may overflow the domain range. You should maybe make the check by sqrt instead?