# Complexity of finding the largest prime factor of a composite number

Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?

• this is an offshoot of the 3rd problem on ProjectEuler.
– ajay
Sep 25 '12 at 5:56
• If the largest prime factor can be found in polynomial time, then applying the same algorithm a linear number of times produces a complete prime factorization, still in polynomial time. So, no, it's not easier. Sep 25 '12 at 6:03

Of course it is easier, since factoring a number into prime powers gives you the largest prime factor for free. In general, it's only a tiny bit easier. There will be extreme examples, like $4^k-1 = (2^k-1)(2^k+1)$, where it might be much easier to prove that one of the numbers is a prime and therefore the largest prime factor, than to factor the other number further.