Last Updated: 2/6/2024, 5:44:57 AM
Photo by Aaron Lee

# Python で素因数分解する

# 考え方

 ひたすら割り続けるだけ  です。 素数の求め方は、こちらを参考にさせていただきました。

約数の記事は、こちらに分離移設しました。

# 実装

２種類用意しました。

# ◯ List[int] 型

これは List[int] 型で返します。

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

n = 2**2 * 3**2 * 5**2
factorize(n)

>> factorize(n)
[2, 2, 3, 3, 5, 5]
>>>

# ◯ List[Tuple[int, int]]

これは List[Tuple[int, int]] で返します。

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

n = 2**2 * 3**2 * 5**2
factorize(n)

>>> factorize(n)
[(2, 2), (3, 2), (5, 2)]
>>>

tuple を使うか list を使うか、すこし悩みました。

Python で素因数分解する
← 素数 約数 →