Python中基于列表理解的素数分解

Question

如何编写一个函数来返回一个元组列表，比如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.takewhile，因为一旦你找到第一个幂，使得{}不是{}的因子，那么后面的任何一个都不会是。这样可以避免log调用。在

有很多方法可以有效地迭代素数（比如说，非常简单的生成器建议使用here，或者可以在{a2}different questions的答案中找到更高性能的版本）。在