Pythonで高速素因数分解〜競プロ用〜
１. はじめに
どうも〜、AtCoder修行中のsnowです。ABC110:D-Factorizationという問題の中で、素因数分解を行う場面があったので、その際に書いたコードをちょっとばかり改変して共有します。
「整数 $N$ の素因数の最大値は高々$\sqrt{N}$以下になる」という性質を利用して、$O(\sqrt{N})$で計算できるように実装していますので、大体の問題には対応できるはずです（多分、、、）。
詳細については、Wikipedia (試し割り方)を確認してください。
2. コード
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
factorization(24)
## [[2, 3], [3, 1]]
## 24 = 2^3 * 3^1
3. おまけ 更なる高速化
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
factorization(24)
## [[2, 3], [3, 1]]
## 24 = 2^3 * 3^1
エラトステネスの篩などの素数列挙アルゴリズムを用いて、事前に素数テーブルを作成しておけば、$\sqrt{N}$以下素数だけの探索で済むので、さらなる高速化が期待できます。
素数列挙には、$O(N\log \log N)$の計算量が掛かりますが、素因数分解を複数回行う必要がある際には検討してみても良いでしょう。
Author And Source
この問題について(Pythonで高速素因数分解〜競プロ用〜), 我々は、より多くの情報をここで見つけました https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .