【Python 3】14行で素因数分解

意外とPythonの標準ライブラリに素因数分解ってないんですね。
Counterを使ってシンプルに書いてみました。上から14行で。

prime_factorization.py

from math import sqrt
from collections import Counter

def prime_factorization(n):
    counter = Counter()
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            counter[i] += 1

    if n != 1:
        counter[n] += 1

    return list(counter.items())

def prime_factors(n):
    return set(map(lambda x: x[0], prime_factorization(n)))

if __name__ == '__main__':
    # 2020 = 2^2 * 5^1 * 101^1
    print(prime_factorization(2020)) # => [(2, 2), (5, 1), (101, 1)]
    print(prime_factors(2020)) # => {2, 101, 5}
    # 1の場合はからのリストを返す
    print(prime_factorization(1)) # => []

参考

Pythonで高速素因数分解〜競プロ用〜