2つの数のk番目の公約数を求めるアルゴリズムとC言語での実装方法

プログラミングの定番問題の一つに、「2つの整数 x と y が与えられたとき、それらに共通する約数(公約数)のうち、小さい方から数えて k 番目の値を出力する」というものがあります。この記事では、その考え方と具体的な実装方法をわかりやすく解説します。

問題の例

たとえば x = 9、y = 18、k = 2 が入力として与えられた場合を考えてみましょう。

9 の約数 : 1, 3, 9
18 の約数 : 1, 2, 3, 6, 9, 18
公約数 : 1, 3, 9
→ 2番目の公約数は「3」

このように、まず両方の数の約数を確認し、共通して現れる値を小さい順に並べれば、k番目の公約数が求まります。なお、最も大きい公約数は最大公約数(GCD)と一致します。

アルゴリズム

効率的に求めるための基本的な手順は以下の通りです。

1. x と y のうち小さい方の値を num とする(公約数は必ず num 以下になるため)
2. i を 1 から num まで順番に調べる
3. x を i で割った余りが 0 で、かつ y を i で割った余りも 0 であれば、i は公約数なのでカウントを 1 増やす
4. カウントが k に達した時点の i が答えとなる
5. ループが終了しても見つからなければ、k番目の公約数は存在しない(例:-1 を返す)

C言語による実装例

#include <stdio.h>

int main(void) {
    int x = 9, y = 18, k = 2; // 2つの数と、求めたい公約数の順位 k
    int num, count = 0;

    // 小さい方の値を num に設定
    if (x < y)
        num = x;
    else
        num = y;

    // 1 から num まで順に公約数かどうかを判定
    for (int i = 1; i <= num; i++) {
        if (x % i == 0 && y % i == 0) { // 両方で割り切れたら公約数
            count++;
            if (count == k) {
                printf("%d番目の公約数は %d です\n", k, i);
                return 0;
            }
        }
    }

    printf("%d番目の公約数は存在しません\n", k);
    return -1;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

2番目の公約数は 3 です

計算量のポイント

この手法では、小さい方の数を N としたとき、ループを最大 N 回回すため計算量は O(N) となります。数がそれほど大きくなければ十分実用的ですが、より大きな数を扱う場合は、ユークリッドの互除法で最大公約数を求め、その約数を列挙する方法の方が効率的です。