1355. The Largest Prime Factor
Print the largest prime factor of n.
12 -> 3
13195 -> 29
1024 -> 2
97 -> 97
Finding every factor and taking the biggest is more work than needed. Divide them out from the bottom instead:
for d from 2 while d*d <= n:
while n is divisible by d:
remember d
n = n / d
if n > 1: n itself is the largest
Two things make this fast and correct. Dividing as you go shrinks n, so the
loop bound d*d <= n tightens continuously and a number like 2^40 finishes
almost immediately. And whatever survives the loop is prime and larger than
every factor removed, so it is the answer outright.
That final check is the part that gets forgotten, and it matters most on the
inputs that look hardest. 600851475143 has its largest factor found inside the
loop, but a large prime input leaves everything to that one line.
The intermediate value must be 64-bit throughout, since n reaches 10^12 and
d*d is compared against it.
Constraints - `2 ≤ n ≤ 1000000000000`
Input
One line containing the integer n.
Output
Print the largest prime factor of n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.