P203: Determine the prime factors of a given positive integer (2)
质因数分解，但结果以[因数，重复数]形式展现。照例先写测试用例：
from python99.arithmetic.p203 import prime_factors_mult
def test_prime_factors_mult():
assert prime_factors_mult(315) == [(3, 2), (5, 1), (7, 1)]
在P202中，已经实现了一个质因数分解方法，其返回形如[3, 3, 5, 7]的结果。现祇需在其结果上再加处理，分组统计列表中相同因数的数量，再以类如[[3, 2], [5, 1], [7, 1]]的形式展示即可。
质因数分解代码实现：
# Determine the prime factors of a given positive integer
# Construct a flat list containing the prime factors in ascending order
from python99.arithmetic.p201 import is_prime
def prime_factors(n):
return prime_factors_internal(n, 2)
def prime_factors_internal(n, prime):
if is_prime(n):
return [n]
if n % prime == 0:
return [prime]+prime_factors_internal(n/prime, prime)
else:
return prime_factors_internal(n, next_prime(prime))
# Bertrand's postulate
def next_prime(n):
for i in range(n+1, 2*n):
if is_prime(i):
return i
return None
在P110「Run-length encoding of list（游程编码）」中，已经实现了相似的功能。我们可以重用其中的方法。分解后的质因数列表中的数都是按序排列的，也就是说「重复的元素一定都是连续的」。首先，将质因数列表中的连续重复元素分组：然后，将分组逐个转换为[E, N]项，E为质因数值，N为E重复的次数。
在P109中已经实现了列表中连续重复元素分组，这里可以直接重用。
「将分组逐个转换为[E, N]项」可以使用Python内建的List Comprehension实现。List Comprehension的本意是提供一种简练的方式创建列表。常见的用法是将一些操作作用于列表中的每一个元素，然后把这些结果拼接成新的列表。List Comprehension的一般行式为：
[f(x) fro x in l]
f是某个函数，接受输入x，输出任意类型。函数f可以为空，也可以直接是表达式x局部变量，用于引用l中的每一个元素l列表
本例中，x是包含一至多个相同元素的列表，而f则要返回一个包含两个元素的列表，第一个元素是x中的任意一个元素「这里简单点就选头元素」，第二个元素是列表x的长度。f可以直接用表逹式实现为：
[x[0], len(x)]
完整的代码实现：
# Determine the prime factors of a given positive integer(2)
# Construct a list containing the prime factors and their multiplicity
from python99.arithmetic.p202 import prime_factors
from python99.lists.p109 import pack
def prime_factors_mult(n):
return [(group[0], len(group)) for group in pack(prime_factors(n))]