今回は Python で素因数分解をしてみます。
素因数分解とは
Wikipedia によると素因数分解とは、
素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。
素因数分解には次のような性質がある。
・任意の正の整数に対して、素因数分解はただ 1 通りに決定する（素因数分解の一意性）。
・素因数分解の結果から、正の約数やその個数、総和などを求めることができる。
https://ja.wikipedia.org/wiki/%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3
とあります。
正の整数を素数に分解するということですね。
ウィキペディアにもありますが、「48」を素因数分解すると、
となります。
Python で素因数分解をするには、SymPy というライブラリを使う方法が簡単です。
SymPy は、公式サイトの説明を和訳すると、
SymPy は記号数学のための Python ライブラリです。SymPy は全機能を備えた計算機代数システム（CAS）を目指していますが、理解しやすく簡単に拡張できるように、コードはできるだけシンプルに保っています。SymPy は完全に Python で書かれています。
https://www.sympy.org/en/index.html
とのことです。
インストール
SymPy は外部ライブラリなので、pip 等でインストールが必要です。
pip install sympySimPy という似た名前のライブラリもあるので、間違えないように気をつけてください。
今回使用するライブラリは SymPyです。
Google Colaboratory にはデフォルトで SymPy がインストールされています。
SymPyで素因数分解してみる
それでは本題の素因数分解をしてみます。
まずはウィキペディアにもあった「48」を素因数分解してみます。
素因数分解には SymPy の factorint()関数を使います。
import sympy
pf_48 = sympy.factorint(48)
print(pf_48){2: 4, 3: 1}factorint()関数は結果を辞書（dict）形式で返します。
key が素数、value が key の素数を積算する回数になっていて、
「48」を素因数分解すると「2 × 2 × 2 × 2 × 3」となり、「24×3」となります。
「100」、「113」、「12321」を素因数分解すると、次のようになります。
import sympy
print(sympy.factorint(100))
print(sympy.factorint(113))
print(sympy.factorint(12321)){2: 2, 5: 2}
{113: 1}
{3: 2, 37: 2}簡単ですね。
「123212321232123212321」などの非常に大きな値でも一瞬で計算してくれるので、
Python で素因数分解をしたい時は SymPy がオススメです。
Google Colaboratory
本記事に掲載しているコードは Google Colaboratory で動作を確認しています。
下記リンクからアクセスして、ご自身の Google ドライブにコピーしていただければ、すぐに実行できます。
環境構築の不要な Google が提供している Web サービスなので、Python を学習中の方にはオススメです。
おわりに
今回は、
SymPy というライブラリを使用して、Python で素因数分解をする方法
をご紹介しました。
SymPy はほとんど使用したことが無かったのですが、方程式を解いたり、微分・積分ができるようなので、また触れる機会があれば紹介したいと思います。
以上です。
コメント