从质因数中找出一个数的所有因数

Question

使用椭圆曲线分解（在 Python 中）我能够在 ~0.5 秒内找到 50 位数字的质因数。有什么方法可以将质因数转换为因数？

我通过测试小数字（496 和 28）、按特定顺序将质因数相乘而实现的。然后将这些数字相乘几乎可以得到因数，但它不是很灵活，因为我只是从一小部分质因数 (1,2,3,5) 中得到了我需要相乘的公式。

Answer 1

也许您正在寻找幂集中每个（唯一）集合的乘积。因此，对于 18=2*3*3，您想要 {{},{2},{3},{3},{2,3},{2,3},{3,3},{2,3,3}} 中每个集合的产品，从而得到 {1, 2, 3, 3, 6, 9, 18}.

Answer 2

这是我的版本，它计算素因子集的幂集的元素乘积，只保留那些唯一的乘积：

def divisors(n, fs=[]):
    if fs == []: fs = factors(n)
    divs = [1]
    for f in fs:
        temp = divs[:]
        for d in divs:
            if f * d not in temp:
                temp.append(f*d)
        divs = temp
    return sorted(divs)

它正在运行：

>>> factors(496)
[2, 2, 2, 2, 31]
>>> divisors(496)
[1, 2, 4, 8, 16, 31, 62, 124, 248, 496]
>>> factors(28)
[2, 2, 7]
>>> divisors(28)
[1, 2, 4, 7, 14, 28]

Answer 3

如果数被分解为素数的幂，例如 p^a q^b r^c 那么该数的可能因式是所有形式为 p^x q^y r^z 的数，其中 0 ≤ x ≤ a， 0 ≤ y ≤ b，且 0 ≤ r ≤ z。

因为你可以有不同数量的质因数，所以这是一个小编程问题。玩得开心。

Answer 4

您可以像这样使用 sympy 模块：

import sympy
sympy.ntheory.factorint(4960) #Factorization.
sympy.ntheory.divisors(4960) #List all divisors.

从质因数中找出一个数的所有因数

Find all the factors of a number from the prime factors

math

factors