在 Python 中使用列表推导进行质数分解

Question

如何编写一个函数，其中 returns 元组列表，例如 (c_i, k_i) for n 使得 n = c1^k1 * c2^k2 * .. .,ci是质数.
例如：12600 = 2^3 * 3^2 * 5^2 * 7^1
期望的输出：[(2, 3), (3, 2), (5, 2), (7, 1)]
我知道如何用 while 做到这一点，但是 是否可以使用列表推导来做到这一点？ 此任务不需要效率 ciency。

# 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.takewhile（例如 itertools.count），因为一旦找到第一个幂使得 prime**power 不是 n、none 后面的将是其中之一。这样您就可以避免调用 log。

并且有一大堆方法可以有效地迭代素数（例如，参见非常简单的生成器建议 here, or higher performance versions that you can find in the answers to a few different questions here on SO）。

在 Python 中使用列表推导进行质数分解

Prime factorization using list comprehension in Python

python

python-3.x

list-comprehension

factorization