python - 在 Python 中分解一个数字

Question

这是我的代码:

def factorize(n):
    sieve = [True] * (n + 1)

    for x in range(2, int(len(sieve) ** 0.5) + 1):
        if sieve[x]: 
            for i in range(x + x, len(sieve), x):
                sieve[i] = False

    lowerPrimes = i for i in range(2, len(sieve)) if sieve[i]] and (n % i == 0)]
    return lowerPrimes

factorize(n) 返回给定值 n 的所有质因数。如您所见，它首先对 n 进行 Eratosthenes 筛法，然后使用列表推导式返回筛法中作为 n 因子的所有值。它为此目的工作得很好，但是，我希望它返回一个列表，这样如果您将其中的每个项目相乘，结果就是 n。你明白我的意思吗？

例如，factorize(99020) 返回 [2, 5, 4951]，但我希望它返回 [2, 2, 5 , 4951]，作为 2*2*5*4951 = 99020。

我知道我的方法还差得远，但你能帮我实现吗？

Answer 1

the answer by Blender中的代码非常好，但该算法在一个非常重要的方面缺乏:它测试太多。例如。试图因式分解 n=392798360393 , 这是一个质数，它会尝试将它除以它下面的所有数字(包括它自己)。这将花费很多时间。

真的有必要吗？如果n == a*b和 a < b , 找到了 a我们真的不需要测试除法 n通过 b .我们知道它也划分n ，因为 n/a == b暗示 n/b == a .所以我们只需要测试while势因子a小于(或等于)潜在因子 b .也就是说，直到达到数字的平方根。

此外，对于每个减少的 n，不是从 2 开始可以start from the previous value of i :

from math import sqrt
def factors(n):    # (cf. https://stackoverflow.com/a/15703327/849891)
    j = 2
    while n > 1:
        for i in range(j, int(sqrt(n+0.05)) + 1):
            if n % i == 0:
                n //= i ; j = i
                yield i
                break
        else:
            if n > 1:
                yield n; break

的确，保理9000009通过此代码在 Ideone 上花费 0.08 秒，而不是 0.59 秒。

这保证只产生质数(因为我们将找到的每个因子分开，并且我们以非递减顺序尝试候选)。如果我们一次对多个数字进行因式分解，那么首先生成素数然后仅通过素数进行测试(a.o.t. 测试所有数字，如上所述)的开销将是值得的；对于仅对一个数字进行因式分解可能不值得，这取决于您的主要一代的速度。

---

但是，当同时对多个数字进行因式分解时，真正应该做的是首先创建最小因子筛，我们在给定范围内标记每个数字它的最小(主要)因子(由筛子从中生成)而不是仅由 True或 False就像埃拉托色尼的筛法一样。这个最小的因子筛然后用于有效分解每个给定的数字，在相同的范围内，通过连续除以它们的因子，从最小的向上，通过在筛子中直接查找而不是测试可以有效地找到这些因子重新:

def sfs_factorize(nums):
    top = max(nums)
    sv = smallest_factor_sieve(top)
    for k in nums:
        fs = [] ; n = k
        while n > 1:
            f = sv[n]    # no testing
            n //= f
            fs.append(f)
        print( k, list(fs))