note.nkmk.me

Pythonで素因数分解(試し割り法)

Date: 2019-08-04 / tags: 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は十分速いといえる。

スポンサーリンク
シェア
このエントリーをはてなブックマークに追加

関連カテゴリー

関連記事