Problem #3
Difficulty: 5%
Largest Prime Factor
Solution Language: Java
The problem
Find the largest prime factor of 600851475143.
My solution
Trial division that divides each factor out as soon as it is found. Every time a divisor i divides the remaining number, I divide it out completely and record i as the latest factor. When the remaining number reaches 1, the last factor recorded is the largest one.
while(num > 1) {
while(num % i == 0) {
num /= i;
answer = i;
}
i += 2;
}
Because factors are removed in increasing order, any i that divides the remainder must be prime: all of its own smaller prime factors were already divided out.
600851475143 isn’t divisible by 2, 3 or 5, so the search starts at i = 7 and steps through the odd numbers.