2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael May 10 '12 at 14:15
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ From a computational complexity point of view there is no gain, but from the execution time would surely be faster if (the non-sophisticated form of) dynamic programming is used. $\endgroup$ – Dave Clarke May 6 '12 at 20:45
  • $\begingroup$ That's not so clear, since it requires you to actually factor all smaller integers. Might or might not be true. $\endgroup$ – Yuval Filmus May 7 '12 at 0:13
  • 1
    $\begingroup$ But the question asks for the factors of all integers from 1 to N, hence you are required to factor all smaller integers. $\endgroup$ – Dave Clarke May 7 '12 at 5:42

Your Answer

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