Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an algorithm were to reduce the number of possible primes $<\sqrt{n}$ which could be a factor of n by 1/2 with each step, then the worst-case-scenario computing time is minimised. As $n\rightarrow \infty$ the number of primes to check approaches $\frac{2\sqrt{n}}{\ln{n}-\ln{2}}$. Hence, if each step were to eliminate half the possibilities, the number of steps taken to factorise n would tend towards $\log_{2} {(\frac{2\sqrt{n}}{\ln{n}-\ln{2}})}$.

What similar lower bound would the factorising time tend towards if n were known to have 3 prime factors, or 4 prime factors?

share|cite|improve this question
Um, how exactly is it reducing the number of possible factors by 1/2 each step? No algorithm I know of does this. – Craig Oct 5 '11 at 15:42
Ignoring the point that Craig raised that this isn't actually possible, you could derive a bound by simply iterating the algorithm. If you have eg 4 factors, run it, find a factor. Divide n by this factor, repeat. – Ragib Zaman Oct 5 '11 at 15:50
@Craig No known algorithm can. The point is that it is impossible for any algorithm to factorise n in fewer steps than that for every n. – Angela Richardson Oct 6 '11 at 8:58
Why is that? I'm not seeing that as being immediately obvious. – Craig Oct 6 '11 at 18:33

Your Answer


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

Browse other questions tagged or ask your own question.