Project Euler | Problem Three
Problem Three
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
The trick here is that you don’t need to care about prime numbers, because any number that you test that is not a prime will already have been divided out by its prime factors.
Essentially you start at the lowest number and any time you come across a factor, you divide it out. Once you divide out and it equals one then the number you just divided out is the largest prime factor.
/**
* The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* @author syfran
* @version %I% %U% %G%
*/
package com.syfran.Euler;
public class ProblemThree extends AbstractEuler
{
private long target = 600851475143L;
public static void main(String [] lol)
{
ProblemThree p = new ProblemThree();
p.start();
}
public long solve()
{
long test = target;
long counter = 1;
while(test != 1)
{
counter++;
while(test % counter == 0)
{
test = test/counter;
}
}
return counter;
}
}
Total RunTime: 2ms
Possible optimizations:
Maybe pregenerating prime numbers, with an extremely efficient algorithm, but I do not think it would work as well.
