python - 所有可能的因素对

Question

我正在尝试编写一个程序，该程序接受一个带有单个前导整数和任意数量的尾随零的数字，然后打印两个因素的所有可能组合。

即。

100

因数是 2^2, 5^2

所以程序会打印:

(2,50),(4,25),(5,20)

或

600

因子是 2^3,3,5^2

(2,300),(4,150),(8,75),(3,200),(5,120),(25,24),(6,100),(12,50),(15,40),(30, 20),(60,10)

...我想这就是全部？是吗？我可以使用一个程序来检查...

import itertools

facts=[[2,2,2],[3],[5,5]]
for n in itertools.product(*facts)
    print(n)

我发现我用错了，但那是我第一次尝试。

这只是给出 (2,3,5) 十次。

我想要 (2) * (2,3,5,5) 和 (2,2) * (3,5.5) 之类的...

Answer 1

To generate all factors of a number given its prime factors :

#!/usr/bin/env python
import itertools, operator

def all_factors(prime_dict):
    series = [[p**e for e in range(maxe+1)] for p, maxe in prime_dict.items()]
    for multipliers in itertools.product(*series):
        yield reduce(operator.mul, multipliers)

例子

prime_dict = {2:3, 3:1, 5:2}
L = sorted(all_factors(prime_dict))
number_of_divisors = reduce(lambda prod, e: prod*(e+1), prime_dict.values(),1)
assert len(L) == number_of_divisors
# -> [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24,
#     25, 30, 40, 50, 60, 75, 100, 120, 150, 200, 300, 600]

生成对:

n, isodd = divmod(len(L), 2)
print(zip(L[:n], reversed(L[n + isodd:])))
if isodd: # number is perfect square
   print((L[n], L[n]))

输出

[(1, 600), (2, 300), (3, 200), (4, 150), (5, 120), (6, 100),
 (8, 75), (10, 60), (12, 50), (15, 40), (20, 30), (24, 25)]

它适用于小数字。您可以使用它来测试您的解决方案，该解决方案可以考虑您数字的特殊形式:x00000...