Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Project Euler problem 7 says:

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 10001st prime number?

I believe that my code is working but very very slow..... I guess increment divisor can be changed but not sure how?

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

namespace p7
{
    //    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 10001st prime number?

    class Program
    {
        //          - SET 'divisor' TO 13
        //          - WHILE( divisor <= ceil[ sqrt(number) ] )
        //          - IF number%divisor == 0 && number != divisor THEN
        //          - Not prime / divisible by 'divisor'
        //          - ELSE IF ceil[ sqrt(number) ] == divisor THEN
        //          - PRIME!!!
        //          - ELSE increment divisor by 2
        static void Main(string[] args)
        {
            Stopwatch sw = Stopwatch.StartNew();
            int count = 6; // we already know 6 primes: 2,3,5,7,11,13 
            long x = 14; // so can look for a prime after number 13

            while (count < 10001)
            {
                if (IsPrime(x, 13))
                {
                    count++;
                    x++;
                }
            }
            Console.WriteLine(x);
            Console.WriteLine("Time used (float): {0} ms", sw.Elapsed.TotalMilliseconds);
            Console.WriteLine("Time used (rounded): {0} ms", sw.ElapsedMilliseconds);
            Console.ReadKey();
        }
        static bool IsPrime(Int64 p, Int64 divisor)
        {
            Int64 sqrt = (Int64)Math.Ceiling(Math.Sqrt(p));
            while (divisor <= sqrt)
           {
                if (p % divisor == 0)
                    return false;
                else if (sqrt == divisor)
                    return true;
                divisor += 2; 
            }
            return true;
        }
    }
}
share|improve this question
add comment

2 Answers

up vote 11 down vote accepted

Your prime testing code is wrong. For example, it would consider 14 to be a prime! You cannot take a shortcut by only testing divisors > 13. Instead:

static bool IsPrime(Int64 p)
{
    if (p % 2 == 0) return false;
    Int64 max = (Int64) Math.Ceiling(Math.Sqrt(p));
    for (Int64 divisor = 3; divisor < max; divisor += 2)
    {
        if (p % divisor == 0) return false;
    }
    return true;
}

Points to note:

  • I use a for loop instead of while, as this better expresses what I'm doing.
  • I only go up to divisor < ceiling(sqrt(p)), which saves one iteration. Not significant, but it's less redundant this way.
  • While I do test for p % 2 == 0, this branch will never be taken because we will later modify our prime number search loop to only search odd numbers. I leave that test here for correctness.
  • Note also that smaller numbers are more likely to be divisors than larger numbers. It's therefore advantageous to test them early.

Your prime search loop looks at each number in from 13 onward. However with the exception of 2, only odd numbers can be primes. We can therefore halve the search time by incrementing in steps of two.

int count = 6;
int targetCount = 10001;
long x;
for (x = 13 + 2; count < targetCount; x += 2)
{
    if (IsPrime(x)) count++;
}

But wait! If we are finding all prime numbers from 13 onward we can use those to speed up our prime test by only testing appropriate prime factors! We can do this by creating a table of primes:

long[] primes = new long[targetCount];
primes[0] =  2;
primes[1] =  3;
primes[2] =  5;
primes[3] =  7;
primes[4] = 11;
primes[5] = 13;

int counter = 6;
for (long x = primes[counter - 1] + 2; counter < targetCount; x += 2)
{
    if (IsPrime(x, primes)) primes[counter++] = x;
}
// the result is in primes[targetCount - 1]

where IsPrime has been changed to

static bool IsPrime(Int64 p, long[] primes)
{
    Int64 max = (Int64) Math.Ceiling(Math.Sqrt(p));
    foreach (long divisor in primes)
    {
        if (divisor > max) break;
        if (p % divisor == 0) return false;
    }
    return true;
}

And hey presto, is this fast! I get 104743 as an answer in a matter of milliseconds.

How did I make this code so fast?

  1. Write correct code without taking bad shortcuts.
  2. Think about what I need and what I have anyway.
  3. Then, figure out an elegant way to connect those two states. Here, my experience with dynamic programming reminded me to build a table of primes.
share|improve this answer
    
104033 is prime, but approximately number 9300. –  ChrisW Feb 2 at 15:35
    
@ChrisW Yes, It should output 104743. I think some prime test may be terminating too early. –  amon Feb 2 at 15:36
1  
(divisor >= max) looks wrong: use (divisor > max) –  ChrisW Feb 2 at 15:36
    
@ChrisW That's it, thanks! –  amon Feb 2 at 15:37
1  
@ChrisW I mostly disagree with using a List: an array should have less overhead, and we precisely know the final size needed. You are right that the divisor > max test is dubious but it is safe as long as the first four primes are already stored inside the array. –  amon Feb 2 at 15:57
show 1 more comment

For such a small prime, you can use a simple sieve of Eratosthenes, which runs in a negligible amount of time for your purposes. The Wikipedia page has a pseudocode implementation. I recommend reading the algorithm description, but not the code, and attempt to correctly implement it for yourself, which shouldn't be too hard.

share|improve this answer
    
A problem with implementing Eratosthenes' sieve is knowing how big to make it, in order to contain the 10001th prime. –  ChrisW Feb 2 at 20:51
1  
@ChrisW: Unless you happen to know that the nth prime number is always smaller than n(ln n + ln ln n) (which in this case tells you it's at most 114319 — not too much wasted effort given the above answer!) –  Micah Feb 2 at 23:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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