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

最大公約数（GCF）は、最大共通除数（GCD）や最高共通因数（HCF）とも呼ばれ、与えられた整数の集合に含まれる各整数を余りなく割り切る最大の正の整数です。たとえば、12 と 18 の GCF は 6 です。6 は 12 と 18 の両方をちょうど割り切る最大の数だからです。 GCF を求める代表的なアルゴリズムは、ユークリッドの互除法と素因数分解です。大きな数では、ユークリッドの互除法のほうが効率的です。この方法は、組 (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 がなぜその値になるのかを理解しやすく、教育的に有用です。 GCF には多くの実用的な用途があります。算術では、分数を最簡分数に約分するために使われます。a/b を簡単にするには、分子と分母の両方を GCF(a, b) で割ります。幾何では、2つの長さの GCF は、どちらも余りなく測れる最長のものさしの長さを表します。コンピューターサイエンスでは、GCF は合同算術、暗号アルゴリズム（RSA 鍵生成など）、データ圧縮に登場します。 3つ以上の数では、GCF は反復的に計算します。GCF(a, b, c) = GCF(GCF(a, b), c) です。この計算機は任意個数の正の整数を扱い、ユークリッドの互除法（高速な結果）と素因数分解（詳細な手順付き出力）の両方に対応しています。素因数分解表示は、因数や割り切れることを学ぶ学生に特に役立ちます。