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

combinatoricselementary-number-theoryprime numbers

$$ \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)$.

Best Answer

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.

(If unlimited numbers of repetitions are allowed, you get an infinite list. It is a somewhat edifying exercise to prove that the sum of the reciprocals of those infinitely many numbers will be finite if you had only finitely many primes in your initial list.)

Related Question