「x ≧ y」が前提で、以下の再帰関数を使えば最大公約数が求まるらしい。
┌──────────────────────────────────────┐
│int gcd(int x, int y) {                                                     │
│    return (y == 0) ? x : gcd(y, x % y);                                    │
│}                                                                           │
└──────────────────────────────────────┘
大きい方から小さい方を削除する。
それを繰り返すだけで最大公約数が求まるってことらしい。
もちろん、最後にきれいにゼロになった時だけで、
そのゼロになる瞬間の直前の値が最大公約数ってこと。
ま、たいていは「1」になってしまうもんだけど、「2」以上の場合もある。
(っていうか「2」以上の場合の方が最大公約数の代表みたいな感じだけど)

以下に例をあげてみた。大きい方か小さい方を削っていくだけだ
┌──────────────────────────────────────┐
│24→ 6→ 6→ 6      ←最大公約数 6                                          │
│18→18→12→ 6→ 0                                                          │
├──────────────────────────────────────┤
│ 4→ 1              ←最大公約数 1                                          │
│ 3→ 3→ 2→ 1→ 0                                                          │
└──────────────────────────────────────┘

大きい方と小さい方が変わらず何回か繰り返す部分があるが
これを端折ってくれるのが剰余(プログラムでいうところの「%」)。
┌──────────────────────────────────────┐
│24→ 6              ←最大公約数 6                                          │
│18→18→ 0                                                                  │
├──────────────────────────────────────┤
│ 4→ 1              ←最大公約数 1                                          │
│ 3→ 3→ 0                                                                  │
└──────────────────────────────────────┘
こんな感じでショートカットしてくれる。

プログラムっていうよりこれ考えたユークリッドが偉い！って感じ。
因数分解とかして求めるより断然速いらしい。

設計の上をいく設計って感じだ。