# Python で約数を求める

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

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

# 1. 書き方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. 書き方2 - 文法

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

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

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

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)

例えば階乗や

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

  • 不自由(たった1行しか書けない)
  • 紛らわしい(引数リストの括弧がない)
  • 普通の関数定義で代用できる。
  • crippled (only one expression)
  • confusing (no argument list parentheses)
  • can use a local function instead

Python Regrets

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
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 式にある、たった1つの利点 (すなわち、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. 書き方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]

$
Last Updated: 11/11/2019, 11:17:29 PM
x 消す
銀河英雄伝説が無料!