查找整数的所有分解的算法

Question

是否有算法可以找到整数的所有因子分解,最好是在Python/Java中,但欢迎任何反馈.

我有一个算法来计算素因子.例如[2,2,5]是主要因素20.

def prime_factorization(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)
            n /= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac

我还有一个算法来计算算法的所有因子(素数和非素数).例如,因素20是[1, 2, 4, 5, 10, 20].

def factors(n):
    a, r = 1, [1]
    while a * a < n:
        a += 1
        if n % a: continue
        b, f = 1, []
        while n % a == 0:
            n //= a
            b *= a
            f += [i * b for i in r]
        r += f
    if n > 1: r += [i * n for i in r]
    return sorted(r)

我正在寻找的是一种返回给定整数的所有因子分解(而不是因子)的算法.对于整数20,算法将产生以下结果:

[1,20]
[2,10]
[4,5]
[2,2,5]

谢谢!

Answer 1

这是一种非常低效的方法。它会生成大量重复项，然后在返回之前将其过滤掉。

这个想法是，您选择包含的因素n=1进行len(factors)乘法，然后重复使用未使用的因素。

import itertools


def mult(fs):
    res = 1
    for f in fs:
        res *= f
    return res


def _generate_all_factorizations(factors):
    if len(factors) <= 1:
        yield factors
        return

    for factors_in_mult in xrange(1, len(factors)+1):
        for which_is in itertools.combinations(range(len(factors)), factors_in_mult):
            this_mult = mult(factors[i] for i in which_is)
            rest = [factors[i] for i in xrange(len(factors)) if i not in which_is]

            for remaining in _generate_all_factorizations(rest):
                yield [this_mult] + remaining

我添加了一个函数来删除重复项并返回它们并很好地排序：

def generate_all_factorizations(factors):
    seen = set()
    res = []
    for f in _generate_all_factorizations(factors):
        f = tuple(sorted(f))
        if f in seen:
            continue
        seen.add(f)
        yield f

现在只需将你的质因数分解输入：

for factorization in generate_all_factorizations([2, 2, 5]):
    print factorization
print "----"
for factorization in generate_all_factorizations([2, 3, 5, 7]):
    print factorization

结果：

(2, 2, 5)
(2, 10)
(4, 5)
(20,)
----
(2, 3, 5, 7)
(2, 3, 35)
(2, 5, 21)
(2, 7, 15)
(2, 105)
(3, 5, 14)
(3, 7, 10)
(3, 70)
(5, 6, 7)
(5, 42)
(7, 30)
(6, 35)
(10, 21)
(14, 15)
(210,)