ユークリッドの互除法とは
1. 最大公約数
2つの自然数があったとします。
例えば$a=50$、$b=30$のとき、$a,b$で大きい方は$a=50$の方です。
このとき次のように式を立てられます。
\begin{align}
a \div b &= c\;あまり\; d\\
a &= b\cdot c + d\tag{1}
\end{align}
今回は(1)式を利用したお話です。
2つの自然数があるとき、「最大公約数」を求めたいとします。
最大公約数は片方の数が小さければ簡単に求められますが、共に大きな数の場合、見つけるのは非常に困難です。
そこでユークリッドの互除法と呼ばれる計算方法を使います。
初めの例で試してみましょう。
$a=50$、$b=30$なので大きな方から小さな方を割ったときを考えます。
\begin{align}
a &= b\cdot c + d\tag{1}\\
50 &= 30\cdot {\color{orange}{1}} + {\color{red}{20}}
\end{align}
このとき、次のように$b$を$a$の位置へ、余りを$b$の位置へ移動します。
これを繰り返します。
すると、
\begin{align}
a &= b\cdot c + d\tag{1}\\
50 &= 30\cdot {\color{orange}{1}} + {\color{red}{20}}\\
30 &= {\color{red}{20}}\cdot{\color{purple}{1}} + {\color{blue}{10}}\\
{\color{red}{20}} &= {\color{blue}{10}}\cdot{\color{green}{2}} + 0
\end{align}
このようになり、余り（+の後ろ）が「$0$」になったら計算終了です。
このとき、$b$の位置にある数（今回なら「$10$」）が2つの自然数の最大公約数になります。
公式っぽく書くと、2つの自然数$a$ , $b$ $(a>b)$があるとき
\begin{align}
a &= b\cdot c_1 + d\\
b &= d\cdot c_2 + e\\
d &= e\cdot c_3 + f\\
\vdots\\
e &= f\cdot c_n + 0
\end{align}
と、計算することができ、余りが$0$になったときの$f$の位置にある数が2つの数の最大公約数です。
2. 最小公倍数
ユークリッドの互除法が分かったところで、今度は最小公倍数を求める方法を紹介します。
例えば、先ほどの例のように$a=50$、$b=30$の場合、最大公約数は「$10$」でした。
ここで、$a$でも$b$でもどちらでも良いのですが、今回は$a$を使うとします。
また、最大公約数を$G=10$として次のように計算します。
\begin{align}
a \div G &= c\tag{2}\\
c\times b &= L\tag{3}
\end{align}
このときに得られる$L$が最小公倍数です。
実際に値を入れて計算してみると、
\begin{align}
50 \div 10 &= 5\\
5\times 30 &= 150
\end{align}
よって、「$150$」が2つの自然数の最小公倍数になります。
C言語で実装
ここまでは数学的な話をしてきましたが、ここからはC言語でユークリッドの互除法を使った計算ができるプログラムを作成していきます。
まず、ここまでの復習として最大公約数は(1)式を繰り返し同じような計算をすると分かりました。ただし、1回の計算が終わるたびに2つの数がズレていくことも分かりました。
次に、最小公倍数は計算したい2つの自然数$a$,$b$と先に求めた最大公約数を用いて(2)(3)式を計算すれば良いと分かりました。
これらを元にC言語でコードを書くと以下の通りになります。
#include <stdio.h>
int main(void)
{
int a, b, c; // 変数cは仮代入
printf("整数a,b(a>b)の最大公約数を求めます.\n");
printf("整数aを入力 > ");
scanf("%d", &a);
printf("整数bを入力 > ");
scanf("%d", &b);
int A=a, B=b;
while(1)
{
if(a<b)
{
printf("入力し直してください.\nERROR:a<b\n");
break;
}
if(b==0) // b=0だったときは処理を終了する
{
printf("0で割ってはいけません.\n");
return 0;
}
if(a%b==0)
{
printf("最大公約数 : %d\n", b);
break;
}
else
{
c = a % b;
a = b;
b = c;
}
}
//最小公倍数を求める
c = A / b;
c = c * B;
printf("最小公倍数 : %d\n", c);
return 0;
}
GCCコンパイルして、実行すると
このようになりました！！
答えが合っているか分かりませんが一応動きます。
ここで注意ですが、あまりにも大きい数を使用するとオーバーフローする可能性がありますのでご注意ください。
挑戦できる方はオーバーフローしにくくなるように改良したり、他の言語でユークリッドの互除法を計算するプログラムを組んでみましょう。