# Python で素因数分解する

# 考え方

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

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

# 実装

2種類用意しました。

# ◯ 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 を使うか、すこし悩みました。

Last Updated: 11/11/2019, 11:17:29 PM
x 消す
銀河英雄伝説が無料!