Problem 3: Largest Prime Factor
The integer has prime factors , making it easy to verify the algorithm by hand.
The actual Euler prompt asks for the largest prime factor of . The tester below lets you explore other inputs as well.
How to Solve
Start dividing the number by the smallest candidate factor (2), stripping it out completely before moving on. Whenever a factor does not divide the current value, increment the factor and try again.
You can stop once no longer holds. At that point the remaining value must be prime, so it is the largest factor.
Because the loop never tests factors above the square root of the input, the algorithm runs in time with constant memory usage.
Code Solution
function largestPrimeFactor(number: number): number {
let factor = 2;
while (factor * factor <= number) {
if (number % factor === 0) {
number = number / factor; // divide out this factor completely
} else {
factor++; // move to next possible factor
}
}
return number;
}