Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
this is an offshoot of the 3rd problem on ProjectEuler. –  ajay Sep 25 '12 at 5:56
2  
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. –  mjqxxxx Sep 25 '12 at 6:03

2 Answers 2

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.