2
\$\begingroup\$

The problem statement is as follows

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 10,001st prime number?

My code that follows is what I used to solve this with.

public class Program
{
    static bool IsPrime(long value)
    {
        if (value==2)
            return true;

        if (value % 2 ==0)
            return false;

        long largestPossibleFactor = (long)Math.Sqrt(value);
        for (int possiblePrimeFactor = 3; possiblePrimeFactor <= largestPossibleFactor; possiblePrimeFactor +=2)
        {
            if (value % possiblePrimeFactor == 0)
                return false;
        }
        return true;
    }

    static long GetPrimeOccurence(int NthOccurence)
    {   
        if (NthOccurence==1)
            return 2;

        int primePosition=2;
        long returnValue=0;
        bool numberIsPrime =false;
        for (long testForPrime=3; primePosition <= NthOccurence; testForPrime +=2)
        {
            numberIsPrime = IsPrime(testForPrime);

            if (numberIsPrime && primePosition == NthOccurence)
                returnValue = testForPrime;

            if (numberIsPrime)
                primePosition++;
        }
        return returnValue;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(GetPrimeOccurence(10001));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ If you want, take a look at the en.wikipedia.org/wiki/Sieve_of_Eratosthenes to see another approach to this problem :) \$\endgroup\$ – IEatBagels May 19 '17 at 9:13
  • \$\begingroup\$ That's my solution. Also, it's spelled "Occurrence." \$\endgroup\$ – T145 Oct 15 '17 at 3:54
1
\$\begingroup\$

You can improve the performance of your IsPrime method. Here is a code snippet from the really well put answer of nhgrif

private static bool IsPrime(long value)
{
    if (value < 2) { return false; }
    if (value % 2 == 0) { return value == 2; }
    if (value % 3 == 0) { return value == 3; }
    if (value % 5 == 0) { return value == 5; }
    if (value == 7) { return true; }

    for (int divisor = 7; divisor * divisor <= value; divisor += 30)
    {
        if (value % divisor == 0) { return false; }
        if (value % (divisor + 4) == 0) { return false; }
        if (value % (divisor + 6) == 0) { return false; }
        if (value % (divisor + 10) == 0) { return false; }
        if (value % (divisor + 12) == 0) { return false; }
        if (value % (divisor + 16) == 0) { return false; }
        if (value % (divisor + 22) == 0) { return false; }
        if (value % (divisor + 24) == 0) { return false; }
    }
    return true;
}

You can improve the readability of GetPrimeOccurence, because right now it has some redundant steps:

if (numberIsPrime && primePosition == NthOccurence)
    returnValue = testForPrime;

Why not simply return the value right away instead of creating additional variable?

Also you're lacking validation for your parameter, you cant look for the 0th prime or any negative number.

I would transform it into something like this:

private static long GetNthPrime(int n)
{
    if (n <= 0)
    {
        throw new ArgumentOutOfRangeException(nameof(n));
    }
    if (n == 1)
    {
        return 2;
    }
    int count = 2;
    int currentNumber = 3;
    while (count < n)
    {
        currentNumber += 2;
        if (IsPrime(currentNumber))
        {
            count++;
        }
    }
    return currentNumber;
}
\$\endgroup\$
1
\$\begingroup\$

Aside from using a naive function to find prime, the GetPrimeOccurrence function could use some tightening up. Most specifically the loop should use a shortcut and return as soon as the nth occurrence is reached:

static long GetPrimeOccurence(int NthOccurence)
{   
    if (NthOccurence==1)
        return 2;

    int primePosition=2;
    bool numberIsPrime =false;
    for (long testForPrime=3; primePosition <= NthOccurence; testForPrime +=2)
    {
        numberIsPrime = IsPrime(testForPrime);

        if (numberIsPrime)
        {
            if(primePosition == NthOccurence)
            {
                return testForPrime;
            }
            primePosition++;
        }
    } 
    return 0;
}
\$\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.