List common divisors of two numbers in Python

今更ながら「最大公約数」の英語が複数あることを知る。

G.C.D (Greatest Common Divisor)
G.C.F (Greatest Common Factor)
H.C.F (Highest Common Factor)

英語圏の人はこれで困ったりしないんだろうか?

それはそれとして。

「立体地形図を手作りしてみようかな、っと(9)」で、x軸y軸の両方が割り切れる値、が必要だったのだけれど、公約数のシンプルな求め方、調べたことないなぁと思って。

最大公約数は一撃で求まるのね。fractions モジュールの gcd で。これだけなのよ：

1 >>> import fractions
2 >>> fractions.gcd(150, 225)
3 75

けど欲しいのは、「公約数全部」なわけね。3, 5, 15, 25, 75 のリストが欲しいのです。

どうしたもんかと思っていたが、いつものようにStackOverflowにヒントが。

まず gcd は fractions モジュールの gcd でもいいちゃぁいいんだけれど、これ、少なくとも Python 2.7 では pure Python の、ホントにこれだけなのね：

fractions.gcd (本物)

1 def gcd(a, b):
2     """Calculate the Greatest Common Divisor of a and b.
3 
4     Unless b==0, the result will have the same sign as b (so that when
5     b is divided by it, the result comes out positive).
6     """
7     while b:
8         a, b = b, a%b
9     return a

これはユークリッド互除法そのもの。で、欲しいのは、この最大公約数を求めるだけで終わらせずに、残る公約数も含めリストで返すことなので、fractions モジュールの gcd を呼び出すよりは、この関数をベースに書き換えちゃっても良かろう、と。

StackOverflowにある「divisorsの求め方」として紹介されてるのが、ちょっと入り組んだワンライナー：

75、は、上の結果

1 >>> [d for d in range(2, 75 // 2 + 1) if 75 % d == 0]
2 [3, 5, 15, 25]

若干伝わりにくいので、ここに至る過程を分解してみた：

 1 >>> # まずはリスト内包の基礎のおさらい
 2 >>> [d for d in range(10)]
 3 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 4 >>> [d for d in range(10) if d % 2 == 0]  # 2で割り切れるもの
 5 [0, 2, 4, 6, 8]
 6 >>> 
 7 >>> # ので
 8 >>> [d for d in range(2, 75 // 2 + 1)]
 9 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37]
10 >>> [d for d in range(2, 75 // 2 + 1) if 75 % d == 0]  # 75 を割り切れるもの
11 [3, 5, 15, 25]

よろしいね。ので、こんなかねぇ：

1 >>> def common_divisors(a, b):
2 ...     while b:
3 ...         a, b = b, a % b
4 ...     return [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
5 ...
6 >>> common_divisors(225, 150)
7 [3, 5, 15, 25, 75]