如何生成一个数的所有可能因子乘积？

Question

我在实现一个算法时遇到了困难，这个算法可以给我一个数字的所有可能的乘积。比如说，对于 N=24，这些乘积是：

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

我已经写了一个函数，可以计算出一个给定数字的质因数及其幂次（例如，对于 N=24，质因数是 2^3 和 3^1）。但是我不知道怎么从这些质因数中得到所有的因数组合。

编辑：这是我尝试过的：

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

这里是你问题的最简单解决方案：

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

Answer 2

你没有说明你需要处理的数字大小，也没有提到速度是否重要，不过这里有一个非常简单的、没有优化的解决方案，对于小输入（比如 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 函数 用于计算向量分解。