How to find algorithm for integer factorization if the prime factorization of the integer is given?

437 Views Asked by At

We're given factorization of an integer $x=p_1 \cdot p_2 \cdots p_k$ where $p_1<p_2<\cdots<p_k$ are prime numbers such that the power of any prime numbers is not greater than $1$. For example $30=2\cdot 3\cdot 5$ is legal input while $300 = 2^2\cdot 3\cdot 5$ is not a legal input.

Let $f(x)$ be the number of ways to represent $x$ as a product of integers (not necessarily prime numbers). For example, $f(30)=5$ because $$30=30\cdot 1=2\cdot 3\cdot 5=2\cdot 15=3\cdot 10=5\cdot 6$$

(order is not important).

What could be an algorithm which calculates $f(x)$ given $x=p_1 \cdot p_2 \cdots p_k$?

Ideally the algorithm should use dynamic programming principles but most importantly what would be the recursive formula to find $f(x)$?

1

There are 1 best solutions below

2
On BEST ANSWER

Since you have specified that no prime appears more than once, your product representations correspond exactly to the partitions of the set $\{p_1,p_2,\ldots,p_k\}$.

The number of partitions of a set with $k$ elements is the $k$th Bell number which form sequence A000110 in OEIS.