最大公約数計算機 - 数の最大公約数

最大公約数（GCF）は、最大公約数（GCD）や最高公約数（HCF）とも呼ばれ、与えられた整数の集合の各数を余りなく割り切ることができる最大の正の整数です。たとえば、12 と 18 の最大公約数は 6 です。6 は 12 と 18 の両方をぴったり割り切れる最大の数だからです。 GCF を求める代表的なアルゴリズムは、ユークリッドの互除法と素因数分解の 2 つです。大きな数に対しては、ユークリッドの互除法のほうが効率的です。これは、数の組 (a, b) を (b, a mod b) に繰り返し置き換え、余りが 0 になるまで続ける方法です。最後に残る 0 でない b が GCF です。このアルゴリズムは O(log min(a,b)) ステップで動作するため、非常に大きな整数でも高速です。 素因数分解は、各数を素数のべき乗の積として表し、すべての数に共通する各素数について最小の指数を取り、その積を GCF とします。たとえば、12 = 2^2 * 3、18 = 2 * 3^2 なので、GCF(12, 18) = 2^1 * 3^1 = 6 です。大きな数に対してはユークリッドの互除法ほど効率的ではありませんが、なぜその値になるのかを直感的に理解しやすい方法です。 GCF は実用面でも幅広く使われます。算数では、分数を約分して既約分数にするために使います。a/b を簡約するには、分子と分母を GCF(a, b) で割ります。幾何では、2 つの長さの GCF が、どちらも余りなく測れる最長の目盛りを表します。コンピュータサイエンスでは、GCF はモジュラー算術、RSA の鍵生成のような暗号アルゴリズム、データ圧縮などに現れます。 3つ以上の数の GCF は、段階的に求めます。GCF(a, b, c) = GCF(GCF(a, b), c) です。この計算機は任意個の正の整数に対応し、ユークリッドの互除法（高速）と素因数分解（手順表示）の両方をサポートしています。素因数分解ビューは、因数や割り切れ方を学ぶ学生に特に役立ちます。