Pythonで素因数分解する【ライブラリ＆実装】

ライブラリで素因数分解

Pythonで素因数分解してくれるライブラリとしてはSympyがあります。
(ちなみにSympyは離散事象シミュレーション用のライブラリらしいです。難しそう….)

利用方法は以下のコードの通りです。
factorint()を使うと素因数をkey, 指数をvalueとした辞書を返してくれます。

from sympy.ntheory import factorint

factorized = factorint(5185)
print(factorized)
# {5: 1, 17: 1, 61: 1}

下記のサイトを参考にしました

Fast prime factorization module

I am looking for an implementation or clear algorithm for getting the prime factors of N in either python, pseudocode or anything else well-readable. There are ...

素因数分解の実装

実装も簡単そうだったので、作ってみました。
速さは考えてないので速い方が良ければ改良してください！

間違えていたら教えてくれるとありがたいです🙇‍♂️

ちなみに割る数は素数確認していませんが、そもそも素数でない数で割る時にそれを構成する素数で割ってしまっているので割り切れないという考えで確認していません。

例えば\(246=2\cdot3\cdot41\)で、6でも割ることができますがその時には既に2と3の割られているので、6で割れません。(伝わると良いのですが…)

def factorize(x):
  nums = []
  for i in range(2, x+1):
      while x % i==0:
        nums.append(i)
        x = x / i
  return nums

print(factorize(5185))
# [5, 17, 61]
print(factorize(10))
# [2, 5]
print(factorize(17))
# [17]