最大公約数 (GCD) 計算機
複数の数値の共通する約数の中で、最大のものを瞬時に見つけます。
最大公約数 (GCD) とは？
最大公約数（Greatest Common Divisor, GCD）とは、2つ以上の正の整数に共通する約数（公約数）の中で、最も大きい数のことを指します。英語では HCF (Highest Common Factor) と呼ばれることもあります。
GCDを使う場面
- 分数の約分: 分子と分母をそれぞれの最大公約数で割ることで、最も簡単な形の分数（既約分数）にすることができます。
- タイルの敷き詰め: 長方形の床に正方形のタイルを隙間なく敷き詰める際、可能な最も大きなタイルのサイズを求めるのに使われます。
- リズムと周期: 異なる周期で発生するイベントの共通の周期や、リズムパターンの分析に応用されます。
計算方法 1: 素因数分解
それぞれの数を素因数分解し、共通する素因数をすべて掛け合わせる方法です。
例：12 と 18 の GCD
- $12 = 2^2 \times 3$
- $18 = 2 \times 3^2$
共通する素因数は $2$ と $3$ なので、$GCD = 2 \times 3 = 6$
計算方法 2: ユークリッドの互除法
より大きな数に対して効率的なアルゴリズムです。紀元前300年頃にユークリッドの『原本』で紹介されました。
アルゴリズムの手順:
2つの自然数 $a, b$ ($a \ge b$) について、
1. $a$ を $b$ で割り、余り $r$ を求める ($a = bq + r$)。
2. $r = 0$ ならば、$b$ が最大公約数である。
3. $r \ne 0$ ならば、$a$ を $b$ に、$b$ を $r$ に置き換えて手順1に戻る。
2つの自然数 $a, b$ ($a \ge b$) について、
1. $a$ を $b$ で割り、余り $r$ を求める ($a = bq + r$)。
2. $r = 0$ ならば、$b$ が最大公約数である。
3. $r \ne 0$ ならば、$a$ を $b$ に、$b$ を $r$ に置き換えて手順1に戻る。
この計算機では、入力された数値に対してユークリッドの互除法を順次適用して解を求めています。