Pythonで公約数の列挙

この記事で公約数列挙の仕方が2つあることを学んだのでメモ

qiita.com

公約数の列挙は

1. 二つの整数を割り切れる数をループで探す
2. 最大公約数の約数を列挙する

の２通りあるらしい。 これをPythonで実装してみる。

目次

1.二つの整数を割り切れる数をループで探す

こちらの方法は特に難しいことはなく、二つの整数を割り切れる数を愚直に探索すれば公約数を求めることができる。

def common_divisor(a, b):
    arr = []
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            arr.append(i)
    return arr

print(common_divisor(12, 18))  # [1, 2, 3, 6]

2.最大公約数の約数を列挙する

AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita
この記事によると

二つの整数 a,b の公約数は、a,b の最大公約数の約数である。

とのこと。

つまり、

1. 2つの整数の最大公約数を求めて
2. この最大公約数の約数を列挙

すれば公約数を列挙したことになる。

どうしてこれが公約数になるのかイメージできなかったが、AtCoder Beginner Contest 142 の「D - Disjoint Set of Common Divisors」の解説で図を使った面白い解説があった。

youtu.be

（以下動画の解説をそのまま図にしたもの）

12と18の公約数列挙を考える。 まずは12を素因数分解する。出てきた素数を二次元上に並べて掛け合わせると、掛け合わせた答えが12の約数になっていることがわかる。

同様に18も素因数分解してみる。

二つの表を見ると右上に元となる数(12と18)があり、そこから左下に向かって約数が広がっているという特徴がある。

もう一つの特徴として、二つの表には重なるところがある。実はこの重なったところが12と18の公約数となっている。

そして最大公約数はどこにあるかというと赤枠内の右上にある。

この図のルールとして、右上の数字(緑のマス)の約数は緑マスを最右端として構成される四角形内の数字なので、つまり緑マス6(12と18の最大公約数)の約数は赤枠内の1,2,3,6(12と18の公約数)となる。

これは
「二つの整数 a,b の公約数は、a,b の最大公約数の約数である。」
を意味している。

このことから、繰り返しになるが、

1. 2つの整数の最大公約数を求めて
2. この最大公約数の約数を列挙

を実装すれば公約数を列挙することができる。 最大公約数はmathモジュールのgcdで求めることができる。
約数の列挙は以下記事のコードを使用した。

qiita.com

def divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

import math
print(divisors(math.gcd(12, 18)))  # [1, 2, 3, 6]

---