Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.