Pythonで素因数分解（試し割り法）
Pythonで、試し割り法によって素因数分解を行う方法について説明する。
- 素因数分解（試し割り法）のサンプルコード
- 素数とその個数を取得
- 処理速度（処理時間）の目安
なお、試し割り法はシンプルなアルゴリズムであり、処理速度という点では最適なアルゴリズムではない。
とはいえ、対象とする整数の桁数によっては十分実用に足る。処理速度（処理時間）の目安は最後に示す。
素因数分解（試し割り法）のサンプルコード
試し割り法による素因数分解のサンプルコードを示す。英語版ウィキペディアに掲載されているコードを参考にした。
def prime_factorize(n):
a = []
while n % 2 == 0:
a.append(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
a.append(f)
n //= f
else:
f += 2
if n != 1:
a.append(n)
return a
結果の例は以下の通り。1に対しては空のリスト[]を返すので注意。
print(prime_factorize(1))
# []
print(prime_factorize(36))
# [2, 2, 3, 3]
print(prime_factorize(840))
# [2, 2, 2, 3, 5, 7]
素数とその個数を取得
上述の関数の結果（素因数分解した整数のリスト）に含まれる素数とその個数を取得するには標準ライブラリcollectionsモジュールのCounter型を使う。
import collections
c = collections.Counter(prime_factorize(840))
print(c)
# Counter({2: 3, 3: 1, 5: 1, 7: 1})
素数のリストや個数のリスト、素数とその個数のタプルのリストを取得するにはkeys(), values(), items()メソッドを使う。
print(c.keys())
# dict_keys([2, 3, 5, 7])
print(c.values())
# dict_values([3, 1, 1, 1])
print(c.items())
# dict_items([(2, 3), (3, 1), (5, 1), (7, 1)])
これらのメソッドはdict_keys型などのオブジェクトを返す。for文で回したりする場合はそのまま使用できる。リストに変換したい場合はlist()を使えばよい。
print(list(c.keys()))
# [2, 3, 5, 7]
そのほか、collections.Counterについての詳細は以下の記事を参照。
処理速度（処理時間）の目安
上述の素因数分解を行う関数の処理速度（処理時間）の目安を示す。当然、実行環境によって結果は異なるのであくまでも目安。以下はMacBook Pro (Late 2016)での実行結果。
なお、以下のコードはJupyter Notebook上でマジックコマンド%%timeitを使って計測したもの。Pythonスクリプトとして実行しても計測されないので注意。
試し割り法による素因数分解では $\sqrt{n}$ までの整数で割っていくので、計算量は $O(\sqrt{n})$ 。
同じ桁数の整数を素因数分解しても、含まれる素数が大きいと処理時間は長く、小さいと処理時間は短くなる。
14桁の素数が含まれると1秒（1000ミリ秒）弱かかる。
print(prime_factorize(67280421310721))
# [67280421310721]
%%timeit
prime_factorize(67280421310721)
# 790 ms ± 14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
同じ桁数でも最大の素数が小さいと数ミリ秒。
print(prime_factorize(67280421310722))
# [2, 3, 3, 109, 18401, 1863581]
%%timeit
prime_factorize(67280421310722)
# 1.74 ms ± 4.55 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
10桁の素数の場合は数ミリ秒。
print(prime_factorize(2147483647))
# [2147483647]
%%timeit
prime_factorize(2147483647)
# 4.53 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
ついでにcollections.Counterの処理時間も示しておく。
要素数100個のリストの場合はマイクロ秒オーダー。
l_100 = list(range(100))
%%timeit
collections.Counter(l_100)
# 7.36 µs ± 205 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
要素数10000個だと数百マイクロ秒。要素がバラバラの場合（0 ~ 9999）も、重複要素がある場合（0 ~ 99が100個ずつ）も大差はない。
l_10000 = list(range(10000))
%%timeit
collections.Counter(l_10000)
# 435 µs ± 22.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
l_10000_2 = list(range(100)) * 100
print(len(l_10000_2))
# 10000
%%timeit
collections.Counter(l_10000_2)
# 366 µs ± 3.86 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
少なくとも素因数分解の結果を処理するにはcollections.Counterは十分速いといえる。