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. おまけ 更なる高速化
　エラトステネスの篩などの素数列挙アルゴリズムを用いて、事前に素数テーブルを作成しておけば、$\sqrt{N}$以下素数だけの探索で済むので、さらなる高速化が期待できます。

素数列挙には、$O(N\log \log N)$の計算量が掛かりますが、素因数分解を複数回行う必要がある際には検討してみても良いでしょう。