# Is it possible to use dynamic programming to factor numbers

Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic programming?

• I don't see how dynamic programming can be of use here (What are subproblems? How often do they occur? How do you split and combine partial results?); essentially, you need a recursive solution first. But then, it is probably hard to prove that DP can not help. – Raphael May 10 '12 at 14:15

You can try to find the smallest divisor $d>1$ of $N$ by trial divison. Then the factorization of $N$ is given by that of $d$ and that of $N/d$. Since $N$ is either a prime number or has a divisor $1 < d < \sqrt{N}$, this would solve the problem. Of course, this is a dynamic solution in a very vague sense only - the table of partial results is only used as a cache, not like in "real" dynamic programming algorithms.
An algorithm using dynamic programming for factoring $N$ which proceeds by factoring all integers $1$ to $N$ in order takes time at least $\Omega(N)$. There's a known algorithm that factors integers in $\tilde{O}(N)$, namely trial division. So it doesn't seem worthwhile to pursue the dynamic programming approach as stated.