# Given a finite list of prime factors, what is the fastest way to find all numbers that can be formed from them

$$\text{Let} \ S = \{p_1,p_2,p_3,...,p_n\}$$ $$\text{where} \ p_i \in \Bbb P$$

What is the fastest known method method/algorithm to generate all unique numbers through product operation on $S$?

$\text{Ex}: S= \{3,5,2\}$
Soln:
$3\times5 = 15$
$3\times2 = 6$
$3\times5\times2 = 30$
$5\times2 = 10$

Currently, my ideas hover around generating all subsets of $S$, multiplying all the members in each of them and eliminating the duplicates from the list of numbers so generated. This is $O(2^n)$.

• I assume the primes may not be distinct, correct? – Alex Becker Dec 26 '11 at 7:24
• If there are duplicates, $S$ is a multiset. Let's say $S$ contains $m_j$ copies of $p_j$, where $p_1, \ldots, p_k$ are the distinct members of $S$. Then the numbers you can form are all of the form $\prod_{j=1}^k p_j^{d_j}$ where $d_j$ are integers, $0 \le d_j \le m_j$. There are $\prod_{j=1}^k (m_j+1)$ of them. And it's easy to enumerate them, say in lexicographic order. – Robert Israel Dec 26 '11 at 8:11
• You should realize that in case $S$ has $n$ (distinct) elements, every one of its $2^n$ subsets has a different product, so there are that many elements in your answer. Do you hope to generate them in less than $O(2^n)$ time? That is of course impossible. – Marc van Leeuwen Dec 26 '11 at 10:26
• This book by Nijenhuis and Wilf give an algorithm for systematically enumerating subsets. See this for a FORTRAN implementation of the algorithms in the book. – J. M. is a poor mathematician Dec 26 '11 at 11:47
• @Alex Yes, primes need not be distinct. But ordering is flexible. – check123 Dec 26 '11 at 11:56

If the primes are distinct and repetitions (e.g. $3\times3\times 5$) are forbidden, then going through the whole list of subsets will yield no duplicates, because the fundamental theorem of arithemetic says prime factorizations are unique.