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