Is it possible to use dynamic programming to factor numbers
You can try to find the smallest divisor $d&gt;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 &lt; d &lt; \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.