最大公約数計算機

計算機

2つ以上の数の最大公約数（GCD）とは、それらすべてを余りなく割り切る最大の数です。例えば12と18の最大公約数は6です。このGCD計算機は、どんな数のリストについてもそれを求めます。以下にカンマ区切りで入力してください。

Q&A

最大公約数とは？

2つ以上の整数の最大公約数（GCD）とは、それぞれの整数を割り切る最大の正の整数です。例えば、24と18の最大公約数は6です。最大公約数は分数を最も簡単な形に約分するのに役立ちます。

GCDはどう計算する？

1. 素因数分解

最大公約数は、2つの数の素因数分解を求めて因数を比較することで計算できます。実際には、素因数分解には時間がかかりすぎるため、この方法は小さな数にしか実用的ではありません。

2. ユークリッドの方法

ユークリッドが導入した方法は、a > b となる2つの正の整数aとbについて、aとbの公約数が a – b とbの公約数と同じであるという事実に基づきます。つまり、2つの正の整数の最大公約数を求めるユークリッドの方法は、大きい方の数をその差で置き換え、2つの数が等しくなるまでこれを繰り返すというものです。等しくなった数がその最大公約数です。

3. ユークリッドの互除法

より効率的な方法はユークリッドの互除法で、2つの数aとbの差を、aをbで割った除算（剰余付き除算）の余りに置き換える変形です。この余りを a mod b と表すと、アルゴリズムは (a, b) を (b, a mod b) に繰り返し置き換え、ペアが (d, 0) になるまで続けます。ここで d が最大公約数です。

最大公約数計算機の使い方は？

少なくとも2つの整数を計算機に入力し、Calculate GCDボタンをクリックするだけです。GCD計算機がすぐに結果を表示します。最大公約数の計算には、その種のものの中でも最良のひとつであるユークリッドの互除法を使っています。