【Python】約数を列挙するプログラムを実装してみる

はじめに

実は約数を列挙するプログラムを以前C#で作成したことがあるのですが、Pythonの勉強の一貫としてPythonでもやってみたいと思います。

www.hanachiru-blog.com

シンプルな実装

def get_divisors(n):
    if n < 1:
        return
    for i in range(1, n+1):
        if n % i == 0:
            yield i

これはシンプルに1から入力された値までを「割り切れるか」を調べています。

ちなみに引数が特定の型でなかったり、不正な値のときはエラーを返したほうがいいんですかね？あまりPythonに詳しくないので、とりあえず0以下は早期リターンしていますがどうなのでしょうか。

また使い方はこんな感じ。

num = 124
for item in get_divisors(num):
    print(item)                 # 1 2 4 31 62 124

改良した実装

C#の記事と同じことを書きますが、シンプルな奴は全部を調べているので比較的遅く、計算量はになってしまいます。

ここで約数のある性質を用いて高速化を測ります。

「a が N の約数ならば、も N の約数である」ことを使うと、半分程度の労力で済む。

約数 - Wikipedia

これを利用することで計算量にまで抑えることができます。

def get_divisors(n):
    if n < 1:
        return
    i = 1
    while i * i <= n:
        if n % i == 0:
            yield i
            if i * i != n:
                yield round(n / i)
        i = i + 1

1
124
2
62
4
31

順番がバラバラになってしまうので、もしシンプルな奴みたいに出力したいならソートを行ってください。

追記) 実装するとき 前，後ろ，前，後ろのように追加していけば順番に並んでいきます。

また調べる値が大きくなるにつれてシンプルな奴と改良版の処理時間の差が如実に現れるので、もし良かったら試してみると面白いかもしれません。

さいごに

私自身Python歴が長いわけではないので、もっと良い書き方もできるかもしれません。

是非ご指摘などありましたらコメント等で教えていただけると嬉しいです。

ではまた。