導入：なぜこの技術が重要か
業務アプリケーションを開発していると、ページネーションの計算、在庫管理の配分ロジック、あるいはグラフ描画のスケール調整など、数学的な処理が必要になる場面が多々あります。特に「最大公約数（GCD）」や「最小公倍数（LCM）」を求める処理は、力技でループを回すと計算コストが増大し、パフォーマンス低下の原因となります。本記事では、計算量を劇的に減らす「ユークリッドの互除法」を用いた実装方法を解説します。
基礎知識：ユークリッドの互除法とは
ユークリッドの互除法とは、2つの整数の最大公約数を求めるための古典的かつ極めて効率的なアルゴリズムです。「2つの数 $m, n$（ただし $m > n$）について、$m$ を $n$ で割った余りを $r$ とすると、$m$ と $n$ の最大公約数は、$n$ と $r$ の最大公約数に等しい」という性質を利用します。この性質を繰り返すことで、最後には余りが0になり、その時の除数が最大公約数となります。
実装・解決策
PHPで実装する際は、再帰処理を用いるか、whileループを使用します。実務ではスタックオーバーフローのリスクを避けるため、ループ処理（反復法）で実装するのが一般的です。また、最小公倍数は「(m n) / 最大公約数」という公式を利用して導き出します。
サンプルプログラム
以下は、実務でもそのまま利用可能な最大公約数と最小公倍数の算出関数です。
/
function gcd(int $m, int $n): int {
// 常に $m が大きくなるように入れ替える
if ($n > $m) {
[$m, $n] = [$n, $m];
}
// 余りが0になるまで繰り返す
while ($n !== 0) {
$tmp = $n;
$n = $m % $n; // 余りを計算
$m = $tmp;
}
return $m;
}
/
- 最小公倍数を求める
- @param int $m
- @param int $n
- @return int
/
function lcm(int $m, int $n): int {
// 0による除算を防ぐため、引数が0の場合は0を返す
if ($m === 0 || $n === 0) return 0;
// (m n) / 最大公約数 で算出。先に割ることでオーバーフローを防ぐ
return abs($m / gcd($m, $n) $n);
}
// 使用例
$a = 12;
$b = 18;
echo “最大公約数: ” . gcd($a, $b) . PHP_EOL; // 結果: 6
echo “最小公倍数: ” . lcm($a, $b) . PHP_EOL; // 結果: 36
?>
応用・注意点
1. オーバーフローへの配慮：最小公倍数を求める際、$m n$ を先に行うと、数値が大きくなりすぎて整数型の最大値を超えてしまう可能性があります。そのため、サンプルコードのように先に割り算を行う（$m / gcd n$）のが定石です。
2. 負の数の扱い：入力値に負の数が含まれる可能性がある場合は、`abs()` 関数を使用して絶対値に変換してから計算するようにしてください。
3. PHP 8.x以降の型指定：現代のPHP開発では、`int` 型ヒントを明示することで、バグを未然に防ぐ堅牢なコードになります。
このアルゴリズムを理解しておくだけで、数値計算が必要な機能の実装スピードと品質が格段に向上します。ぜひプロジェクトの共通関数として活用してください。