Project Euler – Problem 3


Find the largest prime factor of a composite number.

Problem:
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My Solution:
This one was a pain in the ass.  I had to do a lot of reading on this one.

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

namespace Euler
{
    class Problem3 : IProblemBase
    {
        //The prime factors of 13195 are 5, 7, 13 and 29.

        //What is the largest prime factor of the number 600851475143 ?

        public Problem3()
        {         

        }

        public string GetAnswer()
        {
            long result = 0;
            long limit = 600851475143;
            long lastResult = limit;

            int divisor = 2;//default smallest prime

            do
            {
                if (lastResult % divisor == 0)
                {
                    //keep dividing it out
                    lastResult = lastResult / divisor;
                    result = lastResult;
                }
                else
                {
                    //find next prime
                    for (int i = divisor + 1; i < limit;i++ )
                    {
                        if (isPrime(i))
                        {
                            divisor = i;
                            break;
                        }
                    }
                }

            } while (divisor < lastResult / divisor);

            return result.ToString();
        }

        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)
            }

        }

    }
}
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: