I'm trying to work through Project Euler and I'm hitting a barrier on problem 03. I have an algorithm that works for smaller numbers, but problem 3 uses a very, very large number.
Problem 03: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
Here is my solution in C# and it's been running for I think close to an hour. I'm not looking for an answer because I do actually want to solve this myself. Mainly just looking for some help.
static void Main(string[] args) {
const long n = 600851475143;
//const long n = 13195;
long count, half, largestPrime = 0;
bool IsAPrime;
half = n / 2;
for (long i = half; i > 1 && largestPrime == 0; i--) {
if (n % i == 0) { // these are factors of n
count = 1;
IsAPrime = true;
while (++count < i && IsAPrime) {
if (i % count == 0) { // does a factor of n have a factor? (not prime)
IsAPrime = false;
}
}
if (IsAPrime) {
largestPrime = i;
}
}
}
Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
Console.ReadLine();
}
For starters, instead of beginning your search at n / 2, start it at the square root of n. You'll get half of the factors, the other half being their complement.
eg:
n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.
long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3;
while( n > 1)
{
if(n % factor == 0)
{
n/=factor;
}else
factor += 2; //skip even numbrs
}
print factor;
This should be quick enough...Notice, there's no need to check for prime...