Pythonで2つの数の公約数の個数を求めるプログラム

問題の概要

2つの整数 a と b が与えられたとき、a と b の両方を割り切る正の整数、つまり「公約数」が何個存在するかを求めます。

例えば、入力が a = 288、b = 240 の場合、出力は 10 になります。これは、両方の数に共通する約数が [1, 2, 3, 4, 6, 8, 12, 16, 24, 48] の10個あるためです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• カウンター変数 res を 0 で初期化します。
• 1 から gcd(a, b) + 1 までの範囲で i をループさせます。
• i が a を割り切り、かつ i が b も割り切る場合、res を 1 増やします。
• 最後に res の値を返します。

ここでのポイントは、「a と b の公約数は必ず最大公約数 gcd(a, b) の約数になる」という性質を利用している点です。この性質により、探索範囲を gcd(a, b) までに限定できるため、無駄のない効率的な計算が可能になります。

実装例

それでは、実際のPythonコードを見てみましょう。

from math import gcd

def solve(a, b):
    res = 0
    for i in range(1, gcd(a, b) + 1):
        if (a % i) == 0 and (b % i) == 0:
            res += 1
    return res

a, b = 288, 240
print(solve(a, b))

入力

288, 240

出力

10

計算量とさらなる改善案

上記のアルゴリズムの時間計算量は O(gcd(a, b)) です。より大きな数を扱う場合は、gcd(a, b) の約数だけを直接調べる方法が有効です。具体的には、1 から √n（n = gcd(a, b)）までの数で n を割り切れるかを確認し、割り切れた場合は i と n / i のペアがどちらも約数になることを利用すれば、計算量を O(√n) まで削減できます。

また、標準ライブラリの math.gcd を使うことで、ユークリッドの互除法による高速な最大公約数の計算を自分で実装する手間も省けます。