Finding Prime Factors of a number in $\log(n)$

$\begingroup$

Only Strategy I am aware of for finding factors efficiently is sieve of eratosthenes but from sieve I first have to pre-compute the prime numbers less than than $\sqrt{n}$. I want to skip this computation and implement an $O(\log(n))$ solution. Is there any such solution?

$\endgroup$ 1

1 Answer

$\begingroup$

No. As determining whether a number $n$ is prime is in $O(n)$, finding a prime factor is obviously also in $O(n)$.

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy