Pythonで素因数分解する方法

Python

2023.10.042023.11.01

本記事ではPythonで素因数分解する方法を紹介します。
Pythonで素因数分解として、自力で実装する方法とSymPyライブラリを使用するケースを考えます。

素因数分解とは
自力で実装する方法
SymPyを利用する方法
まとめ

素因数分解とは

素因数分解を説明する前提として、まずは素数について理解する必要があります。

素数とは1とその数でしかわることのできない数です。
例えば、素数は2, 3, 5, 7, 11,…などが挙げられます。

そして、素因数分解とは、素数の積である数を表すことです。

素因数分解の例は下記のとおりです。
12 = 2 * 2 * 3、92 = 2 * 2 * 23、512 = 2^9

自力で実装する方法

まずは自力で実装する方法を紹介します。素因数分解アルゴリズムには様々な方法があるようですが、今回は試し割法を実装してみます。

試し割法というのは下記のとおりです。

与えられた整数 n (n はこれから素因数分解する整数）に対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う。
https://www.weblio.jp/wkpja/content/%E8%A9%A6%E3%81%97%E5%89%B2%E3%82%8A%E6%B3%95_%E8%A9%A6%E3%81%97%E5%89%B2%E3%82%8A%E6%B3%95%E3%81%AE%E6%A6%82%E8%A6%81

12の素因数分解する例で考えると、2、3、4、…の順で12を割り切れるか試していく方法になります。
これを実装すると下記のようなコードになります。

def prime_factorize(num):
    prime_l = []
    for n in range(2, num+1):
        while (num % n) == 0:
            prime_l.append(n)
            num //= n
    return prime_l

試しにWindows PowerShellで実行してみましょう。