Krdytkyu

Is there an algorithm to determine all distinct factorizations of a number, if both the number and its prime factorization are known?

Example

n = 64

f = 2^6

The factors are:

1, 2, 4, 8, 16, 32, 64

I am not asking for the above. Instead, is there a method to find the following:

• 1 * 64


• 2 * 32


• 2 * 2 * 16


• 2 * 2 * 2 * 8


• 2 * 2 * 2 * 2 * 4


• 2 * 2 * 2 * 2 * 2 * 2


• 4 * 16


• 4 * 2 * 8


• 4 * 4 * 4


• 8 * 8

The above example has one distinct prime factor, but I would like a solution generalized to n distinct prime factors.

Recursively: for each factor $f$ of your number $n$, prepend $(f)$ to all factorizations of $n/f$ where all factors $ge f$...

As pointed out by @Adrian Keister in a comment, what follows doesn't answer the question asked. However, because this answers what is probably an often asked related question, I'll leave it up, at least unless I start getting killed with downvotes $ldots$

Let $N$ be a positive integer with prime factorization

$$ N ; = ; p_{1}^{n_1} p_{2}^{n_2} p_{3}^{n_3} cdots p_{k}^{n_k}$$

Then, including $1$ and $N,$ there are

$$ (n_1 + 1)(n_2 + 1)(n_3 + 1) cdots (n_k + 1) $$

many factors of $N,$ and each factor has the form

$$ p_{1}^{{alpha}_1} p_{2}^{{alpha}_2} p_{3}^{{alpha}_3} cdots p_{k}^{{alpha}_k}$$

where each $alpha_i$ belongs to ${0,,1,,2,,3,, ldots,,n_i }.$

Example: Let $N = 45000 = 2^3 cdot 3^2 cdot 5^4.$ Then the $(3+1)(2+1)(4+1) = 60$ many factors are

$$ 2^0 cdot 3^0 cdot 5^0 ;;;;;;; 2^0 cdot 3^0 cdot 5^1 ;;;;;;; 2^0 cdot 3^0 cdot 5^2 ;;;;;;; 2^0 cdot 3^0 cdot 5^3 ;;;;;;; 2^0 cdot 3^0 cdot 5^4 $$

$$ 2^0 cdot 3^1 cdot 5^0 ;;;;;;; 2^0 cdot 3^1 cdot 5^1 ;;;;;;; 2^0 cdot 3^1 cdot 5^2 ;;;;;;; 2^0 cdot 3^1 cdot 5^3 ;;;;;;; 2^0 cdot 3^1 cdot 5^4 $$

$$ 2^0 cdot 3^2 cdot 5^0 ;;;;;;; 2^0 cdot 3^2 cdot 5^1 ;;;;;;; 2^0 cdot 3^2 cdot 5^2 ;;;;;;; 2^0 cdot 3^2 cdot 5^3 ;;;;;;; 2^0 cdot 3^2 cdot 5^4 $$

$$ 2^1 cdot 3^0 cdot 5^0 ;;;;;;; 2^1 cdot 3^0 cdot 5^1 ;;;;;;; 2^1 cdot 3^0 cdot 5^2 ;;;;;;; 2^1 cdot 3^0 cdot 5^3 ;;;;;;; 2^1 cdot 3^0 cdot 5^4 $$

$$ 2^1 cdot 3^1 cdot 5^0 ;;;;;;; 2^1 cdot 3^1 cdot 5^1 ;;;;;;; 2^1 cdot 3^1 cdot 5^2 ;;;;;;; 2^1 cdot 3^1 cdot 5^3 ;;;;;;; 2^1 cdot 3^1 cdot 5^4 $$

$$ 2^1 cdot 3^2 cdot 5^0 ;;;;;;; 2^1 cdot 3^2 cdot 5^1 ;;;;;;; 2^1 cdot 3^2 cdot 5^2 ;;;;;;; 2^1 cdot 3^2 cdot 5^3 ;;;;;;; 2^1 cdot 3^2 cdot 5^4 $$

$$ 2^2 cdot 3^0 cdot 5^0 ;;;;;;; 2^2 cdot 3^0 cdot 5^1 ;;;;;;; 2^2 cdot 3^0 cdot 5^2 ;;;;;;; 2^2 cdot 3^0 cdot 5^3 ;;;;;;; 2^2 cdot 3^0 cdot 5^4 $$

$$ 2^2 cdot 3^1 cdot 5^0 ;;;;;;; 2^2 cdot 3^1 cdot 5^1 ;;;;;;; 2^2 cdot 3^1 cdot 5^2 ;;;;;;; 2^2 cdot 3^1 cdot 5^3 ;;;;;;; 2^2 cdot 3^1 cdot 5^4 $$

$$ 2^2 cdot 3^2 cdot 5^0 ;;;;;;; 2^2 cdot 3^2 cdot 5^1 ;;;;;;; 2^2 cdot 3^2 cdot 5^2 ;;;;;;; 2^2 cdot 3^2 cdot 5^3 ;;;;;;; 2^2 cdot 3^2 cdot 5^4 $$

$$ 2^3 cdot 3^0 cdot 5^0 ;;;;;;; 2^3 cdot 3^0 cdot 5^1 ;;;;;;; 2^3 cdot 3^0 cdot 5^2 ;;;;;;; 2^3 cdot 3^0 cdot 5^3 ;;;;;;; 2^3 cdot 3^0 cdot 5^4 $$

$$ 2^3 cdot 3^1 cdot 5^0 ;;;;;;; 2^3 cdot 3^1 cdot 5^1 ;;;;;;; 2^3 cdot 3^1 cdot 5^2 ;;;;;;; 2^3 cdot 3^1 cdot 5^3 ;;;;;;; 2^3 cdot 3^1 cdot 5^4 $$

$$ 2^3 cdot 3^2 cdot 5^0 ;;;;;;; 2^3 cdot 3^2 cdot 5^1 ;;;;;;; 2^3 cdot 3^2 cdot 5^2 ;;;;;;; 2^3 cdot 3^2 cdot 5^3 ;;;;;;; 2^3 cdot 3^2 cdot 5^4 $$

In this example, note that the exponents on $2$ come from ${0,,1,,2,,3}$ and the exponents on $3$ come from ${0,,1,,2}$ and the exponents on $5$ come from ${0,,1,,2,,3,, 4}.$ One way to organize the possible choices of choosing exponents is the same way you would when trying all combinations for a combination lock whose unlocking sequence of digits you've forgotten or lost, sometime I've had to do at least twice, and not for fun, when I was a child.

You can iterate through all divisors $d$ of $n$ and then recursively list all factorizations of $n/d$ where every factor is at most $d$. If you want to know how to implement this efficiently, I can code something in c++.