Как я могу сгенерировать все возможные продукты делителей для числа?

Question

Я изо всех сил пытаюсь реализовать алгоритм, который дал бы мне возможные продукты для числа. Например, для N=24 это:

24*1, 12*2, 8*3, 6*4, 4*3*2, 3*2*2*2

Я реализовал функцию, которая вычисляет основные факторы для данного числа с их полномочиями (например, 2^3 а также 3^1 за N=24). Но я не могу понять, как получить комбинации делителей из основных факторов.

РЕДАКТИРОВАТЬ: Вот что я пытался:

def divisors(factors): # prime factors, e.g. [2,2,2,3] for 24
    yield list(factors)

    d = factors.pop()

    for i in range(len(factors)):
        m = [d*factors[i]] + factors[:i] + factors[i+1:]
        yield from divisors(m)

Answer 1

Вы не говорите, с какими размерами вам нужно это работать или скорость ли важна, но вот очень простое неоптимизированное решение, которое должно отлично работать для небольших входов (n меньше чем 10**7, сказать).

def products(n, min_divisor=2):
    """Generate expressions of n as a product of ints >= min_divisor."""
    if n == 1:
        yield []
    for divisor in range(min_divisor, n+1):
        if n % divisor == 0:
            for product in products(n // divisor, divisor):
                yield product + [divisor]

Чтобы объяснить код, подумайте о том, как вы можете сделать это методично вручную. Вы можете начать с продуктов, которые содержат 2, Если n странно, их нет Если n является четным, то мы можем сделать простую рекурсию: найти все возможные разложения n // 2, а затем вывести decomposition * 2 для каждого. Как только мы исчерпали все продукты, содержащие 2мы переходим к продуктам с участием 3, Но здесь есть дополнительное осложнение: на первом этапе мы уже нашли все продукты, включающие 2поэтому, чтобы избежать повторных решений, мы хотим ограничиться продуктами, в которых каждый делитель по крайней мере 3, Таким образом, наш рекурсивный вызов должен отслеживать минимально допустимый делитель, min_divisor выше. Наконец, нам нужен базовый вариант: 1 выражается как пустой продукт.

И вот выход для n=24, в том числе 6*2*2 В случае, если вы пропустили:

>>> for product in products(24):
...     print('*'.join(map(str, product)))
... 
3*2*2*2
6*2*2
4*3*2
12*2
8*3
6*4
24

Это менее чем удовлетворительно, хотя: как отмечали другие комментаторы, должна быть возможность вычислить мультипликативные разбиения n из простой факторизации и даже просто из списка показателей в основной факторизации, используя простые числа только тогда, когда необходимо восстановить факторы. Вот вариант выше, который работает с существующей простой факторизацией. Есть еще много возможностей для повышения эффективности: в частности, itertools.product вызов и последующая фильтрация, чтобы игнорировать все лексикографически меньше, чем min_exponents должен быть заменен пользовательским итератором, который начинается с min_exponents, Но это должно послужить отправной точкой.

import itertools

def exponent_partitions(exponents, min_exponents):
    """Generate all vector partitions of 'exponents', each of whose
    entries is lexicographically at least 'min_exponents'."""
    if all(exponent == 0 for exponent in exponents):
        yield []
    else:
        for vector in itertools.product(*(range(v+1) for v in exponents)):
            if vector >= min_exponents:
                remainder = tuple(x - y for x, y in zip(exponents, vector))
                for partition in exponent_partitions(remainder, vector):
                    yield partition + [vector]


def divisor_from_exponents(primes, exponent_vector):
    """Reconstruct divisor from the list of exponents."""
    divisor = 1
    for p, e in zip(primes, exponent_vector):
        divisor *= p**e
    return divisor


def multiplicative_partitions(primes, exponents):
    """Generate all multiplication partitions of
    product(p**e for p, e in zip(primes, exponents))"""
    if len(exponents) == 0:
        # Corner case for partitions of 1.
        yield []
    else:
        initial_vector = (0,) * (len(exponents) - 1) + (1,)
        for partition in exponent_partitions(exponents, initial_vector):
            yield [divisor_from_exponents(primes, vector) for vector in partition]

И выход для 24опять же мы пишем 24 как 2**3 * 3**1так что кортеж простых чисел (2, 3) и соответствующий кортеж показателей (3, 1),

>>> for product in multiplicative_partitions((2, 3), (3, 1)):
...     print('*'.join(map(str, product)))
... 
2*2*2*3
4*2*3
8*3
6*2*2
12*2
4*6
24

Существует множество литературы по генерации и подсчету мультипликативных разбиений целого числа. См., Например, ссылки из OEIS A001055 и функции SAGE для вычисления векторных разделов.

Answer 2

Вот самое простое решение вашего вопроса:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors