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

Not the answer you're looking for? Browse other questions tagged or ask your own question.