Subset Product- Given $N$ and a list of positive divisors $S$, decide if there is a product combination equal to $N$
- We will sort $S$ in numerical order from smallest to largest in order to find out the maximum combination size to avoid redundancy.
- We will remove non-divisors in $S$. This does not impact the correctness, as no possible combination could yield N if there's a non-divisor in that combination.
Iterate over divisors of $N$ in $S$ and calculate the maximum combination size. We multiply each divisor in $S$ until the product $<=$ $N$
Isn't the sum of the prime exponents the bound for this?
$O(2^{\text{$Max-combination-size$}})$
We only allow one duplicate of 1 in S (any product combination of 1 is always 1) , to prevent redundant combinations and we sort S from smallest to largest which is a requirement to get $Max-combination-size$. $Max-combination-size$ basically ensures we don't do redundant combinations that will always yield a product > $N$. So the algorithm runs in $ O(N^M)$ is substantially smaller in magnitude compared to N.
So, we got an efficient algorithm in the value of N??
So there is a pseudo-polynomial algorithm, I just wanted to know if this is always the case if we look at number theorems when it comes to divisors and the value of N?