最大公約数

２つの正の整数 x と y の最大公約数とは

x / d と y / d の余りがともに 0 となる d のうち最大のもの

を言います。最大公約数は英語で Greatest Common Divisor と言われ、一般的に gcd と略されます。いくつか例を見てみましょう。

gcd(35, 14) = 7

(公約数 1, 7 のうち最大の数である 7)

gcd(128, 192) = 64

(公約数 1, 2, 4, 8, 16, 32, 64 のうち最大の数である 64)

誰もが思いつく最大公約数を求める方法が、以下の力任せのアルゴリズムです。

001 int gcd( int x, int y ){
002     int n;
003     n = min( x, y ); // x と y の小さい方
004     // n から 1 までの数で、x と y を順に割っていき、
005     // 余りが 0 になったらその数を返す
006     for ( int d = n; d >= 1; d-- ){
007         if ( x % d == 0 && y % d == 0 ) return d;
008     }
009     assert ( false ); // 入力に 0 がきたらエラー
010 }

このアルゴリズムは実用的ではありません。