Project Euler – Problem 7


Find the 10001st prime.

Problem:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?

My Original Brut Force Solution knowing nothing about primes SLOW:

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

namespace Euler
{
    class Problem7 : IProblemBase
    {

        //By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13,
        //we can see that the 6^(th) prime is 13.

        //What is the 10001^(st) prime number?

       //The algorithm

       //1. Create a contiguous list of numbers from two to some highest number n.
       //2. Strike out from the list all multiples of two (4, 6, 8 etc.).
       //3. The list's next number that has not been struck out is a prime number.
       //4. Strike out from the list all multiples of the number you identified in the previous step.
       //5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
       //6. All the remaining numbers in the list are prime.

        public Problem7()
        {
        }

        public string GetAnswer()
        {

            int primeCount = 0;
            int result = 0;

            for(int i=2;i>0;i++) //loop forever starting at 1
            {
                int matchCount = 0;
                for (int j = i; j > 0; j--)//loop down from current number to find prime
                {
                    if(i % j == 0)
                    {
                        matchCount++;
                    }

                }
                if (matchCount == 2)//prime
                {
                    primeCount++;
                    result = i;
                    if (primeCount == 10001)
                    {
                        break;
                    }
                }

            }                

            return result.ToString(); ;
        }

    }
}

My Solution after learning about primes and using Sieve of Eratosthenes:

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

namespace Euler
{
    class Problem7 : IProblemBase
    {

        //By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13,
        //we can see that the 6^(th) prime is 13.

        //What is the 10001^(st) prime number?

       //The algorithm

       //1. Create a contiguous list of numbers from two to some highest number n.
       //2. Strike out from the list all multiples of two (4, 6, 8 etc.).
       //3. The list's next number that has not been struck out is a prime number.
       //4. Strike out from the list all multiples of the number you identified in the previous step.
       //5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
       //6. All the remaining numbers in the list are prime.

        public Problem7()
        {
        }

        private bool isPrime(int n)
        {
            if (n==1)
            {
                return false;
            }
            else if (n < 4)
            {
                return true; //2 and 3 are prime
            }
            else if (n % 2 == 0)
            {
                return false;
            }
            else if (n<9)
            {
                return true; //we have already excluded 4,6 and 8.
            }
            else if (n % 3 == 0)
            {
                return false;
            }
            else
            {
                int r= (int)(Math.Floor(Math.Sqrt((double)n))); // n rounded to the greatest integer r so that r*r<=n
                int f=5;
                while (f<=r)
                {
                    if (n % f==0){return false;} //(and step out of the function)
                    if (n %(f+2)==0){return false;} //(and step out of the function)
                    f=f+6;
                }
                return true; //(in all other cases)
            }

        }

        public string GetAnswer()
        {
            int limit = 10001;
            int count=1; //we know that 2 is prime
            int candidate=1;
            do{
                candidate=candidate+2;
                if (isPrime(candidate)) { count +=1; }
            } while(count<limit);

            return candidate.ToString();

        }

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: