6
\$\begingroup\$

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>();

    primes.Add(2);
    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)
            {
                primes.Add(nPrimeVal);
                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);
}
\$\endgroup\$
6
\$\begingroup\$

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)
        {
            primes.Add(nPrimeVal);
            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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy