【Python】素因数分解する関数を作成する

田中太郎
田中太郎

Python で素因数分解する関数を作成しました。

サンプルコード

def detect_prime_number(num):
    """num が素数かどうかを判定する関数"""
    num_max = int(num**(1/2))+1  # 計算量を減らすため、平方根を取る。
    check = True
    for tmp in range(2, num_max):  # 2からnum_maxまでtmp が足される。
        if num%tmp == 0:  # tmp で割り切れたら素数ではない。
            check = False
            break
    return num, check


def factorization(num, num_list):
    """num をnum_listで因数分解する。"""
    result = []
    for element in num_list:
        while True:  # 1つの素数で割れるだけ割る。
            if num % element == 0:
                result += [element]
                num = num / element
            else:
                break
    return result


def prime_number_factorization(input_num):
    """."""
    result = []
    for i in range(2, input_num):
        num, check = detect_prime_number(i)

        if check:
            result += [num]

    print(input_num)
    print(result)

    return factorization(input_num, result)


if __name__ == "__main__":
    print(prime_number_factorization(100))

解説

def prime_number_factorization(input_num):

1入力、1出力

入力:int(素因数分解したい数字)

出力:list(素因数分解された数字のリスト)

制約:2以上の数字を引数にする

def detect_prime_number(num):

1入力、2出力

入力:int(素数を判定したい数字)

出力:int(入力した数字), Bool(素数ならTrue、素数でないならFalse)

制約:2以上の数字を入れる。

def factorization(num, num_list):

2入力、1出力

入力:int(素因数分解したい数字)、List(素数のリスト)

出力:List(因数分解に使用した数字のリスト)

制約:numは2以上の数字にする。num_listは素数のリスト。

出力

100
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
[2, 2, 5, 5]

蛇足

平方根の計算で、num**(1/2) を使っていますが、標準モジュールのmath には、math.sqrt()という平方根を求める関数があります。

計算速度が少しだけ違います。お好みでお使いください。

タイトルとURLをコピーしました