python - 在 Python 中使用列表推导式进行质因数分解

Question

如何编写一个返回元组列表的函数，例如 n 的 (c_i, k_i) ，使得 n = c1^k1 * c2^k2 * ... ，ci 是素数。
例如:12600 = 2^3 * 3^2 * 5^2 * 7^1
所需输出:[(2, 3), (3, 2), (5, 2), (7, 1)]
我知道如何使用 while 来完成此操作，但是是否可以使用列表理解来完成此操作？此任务不需要效率。

# naive function 
def is_prime(n):
    return n > 1 and all(n % i != 0 for i in range(2, n))

# while version
def factorization_while(n):
    res = []
    for i in range(1, n + 1):
        if is_prime(i):
            j = 0
            while n % i == 0:
                n = n // i
                j += 1
            if j != 0:
                res.append((i, j))
    return res

# list comprehension version
def factorization(n):
    return [
        (i, j) for i in range(1, n + 1) if is_prime(i) \
        and n % i == 0 ... # add smth
    ]

Answer 1

我认为这应该不会太难。您实际上不需要修改 n 来找到它的素因数，它们都是完全相互独立的。因此，只需迭代适当的素数，并找到有效的最大功率!

from math import log

def prime_factors(n):
    return [(prime, max(power for power in range(1, int(log(n, prime))+1)
                              if n % prime**power == 0))
            for prime in range(2, n+1) if n % prime == 0 and isprime(prime)]

有几种方法可以进一步改进这一点。您可以在无限幂生成器(例如 itertools.count)上使用 itertools.takewhile，就像您找到第一个幂使得 prime**power 不是 n 的因子，后面的也不会。这将使您避免 log 调用。

有很多方法可以有效地迭代素数(例如，建议使用非常简单的生成器 here ，或者您可以在此处的 a few different questions 的答案中找到更高性能的版本上)。