Tell me more ×
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.
up vote 2 down vote favorite

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
1  
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

1 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.