Last Updated: 2/6/2024, 5:44:57 AM

# Python で約数を求める

３つの書き方を示しました。書き方１がコードが短く、速度も速いのでオススメです。２と３はおまけです。

いずれの書き方でも、まず素因数分解をします。次にその結果のすべての組み合わせを求めれば約数になります。

# 1. 書き方１

コードを読んでいただくよりも、対話モードにコピペてた実行結果を見ていただいた方が、何をしているのか、わかりやすいかもしれません。

# 対話モード >>> に
# コピペで実行できます
def sample_code():
    n = 2**2 * 3**2 * 5**2
    
    print('# 素因数')
    fct = factorize(n)
    print(fct, num(fct))
    
    print('# 約数')
    for div in divisorize(fct):
        print(div, num(div))


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a


if __name__ == '__main__':
    sample_code()

... 
# 素因数
[(2, 2), (3, 2), (5, 2)] 900
# 約数
[(2, 0), (3, 0), (5, 0)] 1
[(2, 0), (3, 0), (5, 1)] 5
[(2, 0), (3, 0), (5, 2)] 25
[(2, 0), (3, 1), (5, 0)] 3
[(2, 0), (3, 1), (5, 1)] 15
[(2, 0), (3, 1), (5, 2)] 75
[(2, 0), (3, 2), (5, 0)] 9
[(2, 0), (3, 2), (5, 1)] 45
[(2, 0), (3, 2), (5, 2)] 225
[(2, 1), (3, 0), (5, 0)] 2
[(2, 1), (3, 0), (5, 1)] 10
[(2, 1), (3, 0), (5, 2)] 50
[(2, 1), (3, 1), (5, 0)] 6
[(2, 1), (3, 1), (5, 1)] 30
[(2, 1), (3, 1), (5, 2)] 150
[(2, 1), (3, 2), (5, 0)] 18
[(2, 1), (3, 2), (5, 1)] 90
[(2, 1), (3, 2), (5, 2)] 450
[(2, 2), (3, 0), (5, 0)] 4
[(2, 2), (3, 0), (5, 1)] 20
[(2, 2), (3, 0), (5, 2)] 100
[(2, 2), (3, 1), (5, 0)] 12
[(2, 2), (3, 1), (5, 1)] 60
[(2, 2), (3, 1), (5, 2)] 300
[(2, 2), (3, 2), (5, 0)] 36
[(2, 2), (3, 2), (5, 1)] 180
[(2, 2), (3, 2), (5, 2)] 900
>>>

# 2. 書き方２ - 文法

もし divisorize で２重リスト内包表記や条件式（三項演算子）を使わないならこんな感じになります。

def divisorize(fct):
    div = []
    if not fct:
        div.append([])
        return div
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct)
    suf_div = [[(b, k)] for k in range(e + 1)]
    for pre in pre_div:
        for suf in suf_div:
            div.append(pre + suf)
    return div

# 2.1. 二重のリスト内包表記

Python では可読性の低い書き方を嫌う文化にあるような気がします。 Effective Python でも「項目8：リスト内包表記には、3つ以上の式を避ける」と述べられていました。でも、これくらい簡単なら使ってもいいかなと思って使いました。確かに読みづらいかも笑。

def divisorize(fct):
    ...
    return [pre + suf for pre in pre_div for suf in suf_div]

def divisorize(fct):
    div = []
    ...
    for pre in pre_div:
        for suf in suf_div:
            div.append(pre + suf)
    return div

二重のリスト内包表記は、二次元リストを１次元にするときにも使ったりします。

lst2d = [[i + 3*j for i in range(3)] for j in range(3)]
lst2d == [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
lst1d = [elm for lst1d in lst2d for elm in lst1d]
lst1d == [0, 1, 2, 3, 4, 5, 6, 7, 8]

# 2.2. 条件式

よく三項演算子と言われるものです。これも、可読性を下げるものの一つであるような気がします。ただ、再帰呼び出しの k = 0 の時の動作を定義する時には、これは結構使えるかなと思ったりもします。 k = 0 のときの動作という、特殊な条件で全体のコードを切ってしまうことがなくなります。

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    ...

def divisorize(fct):
    # いきなり not fct のときなんていう
    # 特殊な条件を示されてもピンとこない。
    if not fct:
        return [[]]
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct)
    ...

条件式 (しばしば "三項演算子" と呼ばれます) は最も優先度が低いPython の演算です。 x if C else y という式は最初に条件 x ではなく C を評価します; C が true の場合 x が評価され値が返されます; それ以外の場合には y が評価され返されます。
6.12. 条件式 (Conditional Expressions) (opens new window)

例えば階乗や

factorial = lambda n: n * factorial(n - 1) if n else 1

def factorial(n):
    if n:
        return n * factorial(n -1)
    else:
        return 1

ユークリッド互除法なんかも、こんな風に書けます。

gcd = lambda a, b: gcd(b, (a % b)) if a % b else b

def gcd(a, b):
    if a % d:
        return gcd(b, (a % b))
    else:
        return b

ただ Guido は lambda 式は嫌いらしいです。

私は lambda が、いいと思ったことがない。
I've never liked lambda

不自由（たった１行しか書けない）

紛らわしい（引数リストの括弧がない）

普通の関数定義で代用できる。

crippled (only one expression)

confusing (no argument list parentheses)

can use a local function instead

Python Regrets (opens new window)

PEP 8 でも lambda は、関数の定義では使用しないように指示されています。 lambda を使用するのは、原則、関数オブジェクトを引数にとる関数に代入するときだけ。また変数などに代入せず、そのまま引数として与えてください。

# OK
list(map(lambda x: x**2, range(10)))

# NG
f = lambda x: x**2
list(map(f, range(10)))

プログラミングにあたっての推奨事項 - PEP 8 (opens new window)
Programming Recommendations - PEP8

lambda 式を識別子に直接束縛する代入文ではなく、常に def 文を使ってっください。
Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.

Yes:
def f(x): return 2*x

No:
f = lambda x: 2*x

最初の形式は、結果としてえられる関数オブジェクトの名前が、一般的な <lambda> ではなく 'f' という名前がつけられていることを意味しています。
The first form means that the name of the resulting function object is specifically 'f' instead of the generic '<lambda>'.

関数オブジェクトに文字列の名前が与えられていることは、一般に例外が発生した時にそれをトレースバックさせたり、関数名を文字列で出力させる際に役立ちます。
This is more useful for tracebacks and string representations in general.

代入文を使うことは（代入文で lambda 式を変数に束縛してから map, filiter などの高階関数に引数として与えることは）、 def 文にはなく lambda 式にある、たった１つの利点 (すなわち、lambda 式は、より大きな式の中に埋め込められるということ)を無意味なものにしてしまいます。
The use of the assignment statement eliminates the sole benefit a lambda expression can offer over an explicit def statement (i.e. that it can be embedded inside a larger expression)

# 3. 書き方３ - データ構造

素因数分解 factorize が返すデータ構造を [(2, 2), (3, 2), (5, 2)] ではなく [2, 2, 3, 3, 5, 5] にして実装して見ました。しかし約数を求める速度が 10 倍、遅くなってしまいました笑

約数を求めるときは、[(2, 2), (3, 2), (5, 2)] として取り扱った方が良さそうです。しかし、それ以外の場合は、[2, 2, 3, 3, 5, 5] として取り扱っても、いいかなという気もします。シンプルですしね。

def factorize_naive(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


def divisorize_naive(fct):
    # bit list
    bit_len = len(fct)
    r = range
    bit_list = [[(i >> j) % 2 for j in r(bit_len)] for i in r(2**bit_len)]
    # divisor
    div = [[f for f, b in zip(fct, bit) if b] for bit in bit_list]
    div[0] = [1]
    # exclude duplication, such as  [2, 2, 0], [2, 0, 2], [0, 2, 2].
    div = [list(t) for t in set([tuple(d) for d in div])]
    return div


def num_naive(fct):
    a = 1
    for b in fct:
        a = a * b
    return a

# 4. 速度比較

結果は、以下のような具合です。

git clone https://github.com/niconico25/comparison_of_python_code/
cd comparison_of_python_code
python3 9_1_divisor.py

$ python3 9_1_divisor.py 

# Case 0
# (2**2 * 3**2 * 5**2,)
_divisorize_pair                         :   0.0421 [msec]
_divisorize_syntax                       :   0.0440 [msec]
_divisorize_naive                        :   0.1716 [msec]

# Case 1
# (2**2 * 3**3 * 5**3,)
_divisorize_pair                         :   0.0691 [msec]
_divisorize_syntax                       :   0.0725 [msec]
_divisorize_naive                        :   0.7191 [msec]

# Case 2
# (2**2 * 3**3 * 5**4,)
_divisorize_pair                         :   0.0858 [msec]
_divisorize_syntax                       :   0.0897 [msec]
_divisorize_naive                        :   1.5025 [msec]

# Case 3
# (3313**2 * 3323**3,)
_divisorize_pair                         :   0.9267 [msec]
_divisorize_syntax                       :   0.9269 [msec]
_divisorize_naive                        :   0.8647 [msec]

# Case 4
# (3313**3 * 3323**4,)
_divisorize_pair                         :   0.9860 [msec]
_divisorize_syntax                       :   0.9867 [msec]
_divisorize_naive                        :   1.1727 [msec]

# Case 5
# (3313**3 * 3323**5,)
_divisorize_pair                         :   1.0217 [msec]
_divisorize_syntax                       :   1.0259 [msec]
_divisorize_naive                        :   1.5693 [msec]

$

9_1_divisor.py - GitHub (opens new window)

← 素因数分解エラトステネスの篩 →