Find all ways to write a number as multiply of numbers

Question

Find all ways to write a number as multiply of numbers (different from 1).

For example:

12 = 12, 12 = 2 * 6, 12 = 3 * 4, 12 = 2 * 2 * 3

I have no idea how to this problem and I have spend days reading about factors, sieves and similar topics

If you need help to make a program that solves this, you need to be *way* more specific, and also show what have you tried and what isn't working; this questions looks like simply seeking someone to solve a homework problem and those questions are usually frowned upon. If you need to solve this mathematically, then you're asking in the wrong site. Perhaps you can find help on [Math.SE](https://math.stackexchange.com/) — Josh Part, Aug 16 '18 at 15:07
Possible duplicate of [How to find multiplicative partitions of any integer?](https://stackoverflow.com/questions/8558292/how-to-find-multiplicative-partitions-of-any-integer) — Joseph Wood, Aug 17 '18 at 23:48

score 0 · Answer 1 · answered Aug 20 '18 at 01:04

A simplistic recursive approach:

def get_equations(n):
    equations = set()

    quotient, remainder = divmod(n ** 0.5, 1)

    for divisor in range(n - 1, int(quotient if remainder else quotient - 1), -1):

        quotient, remainder = divmod(n, divisor)

        if remainder == 0:

            equations.add(tuple(sorted([divisor, quotient])))

            for sub_equation in get_equations(divisor):
                equations.add(tuple(sorted([*sub_equation, quotient])))

    return equations

print(get_equations(12))
print(get_equations(25))
print(get_equations(81))

OUTPUT

> python3 test.py
{(2, 2, 3), (2, 6), (3, 4)}
{(5, 5)}
{(3, 3, 9), (3, 3, 3, 3), (3, 27), (9, 9)}
>

Instead of explicitly going after the prime divisors first, like all the suggestions in the cited duplicate, I just let it all play out. Not optimal (should avoid duplication rather than use sets to eliminate it) but simple enough to write and doesn't require days of research.

I didn't include your '12 = 12' result as it's really '12 = 12 * 1' and you said 'different from 1'.

Find all ways to write a number as multiply of numbers

1 Answers1