ユークリッドの互除法を思い出して実装する
概要
ユークリッドの互除法をC++で実装する。ユークリッドの互除法は数の大きい2数の最大公約数や、3数の最大公約数を求めるなどの場面で便利に使える。
なお、この記事でユークリッドの互除法自体の証明とかはやらないので注意。
動機・経緯
アルゴリズムの講義でユークリッドの互除法を思い出しておいてねと言われたので復習。以前ＡＢＣでそういった問題を解いた記憶があったのでプログラムを漁って持ってきた。
内容
ユークリッドの互除法の手法
片方の数を割った余りをもって割った数を割る。これを繰り返す。余りは試行するほどに小さくなっていくので必ずいつかは終わる。余りが0になったら終了。機械的に実行できるのでプログラムの実装はかなり簡単。
プログラムの実装
実装はシンプル。二つの数を受けて
プログラム(C++)
#include <iostream>
using namespace std;
int main(){
int ia,ib,iSurplus;
cin >> ia >> ib; //二つの数を受ける。
iSurplus = ia % ib; //剰余 を求める
while(iSurplus != 0){ //剰余が0になるまで続ける。
ia = ib;
ib = iSurplus;
iSurplus = ia % ib;
}
cout << ib << endl; //剰余 が0になったら最後に割るのに使った数を出力する
return 0;
}
実行結果
C:\Users\horis\Desktop>g++ -o Euclid Euclid.cpp -Wall -Werror C:\Users\horis\Desktop>Euclid 2020 ← 入力1 856 ← 入力2 4 ← 出力
3数の最大公約数を求める
以前ABCで出題された問題。3数の最大公約数を求めている。方法としては先にの2数の最大公約数を計算して、その最大公約数と
の最大公約数を計算することで
全体の最大公約数を求めている。
プログラム
#include<iostream>
using namespace std;
int main (){
int K,surp,temp,sum,save_a,save_b,save_c;
sum = 0;
cin >> K;
for(int a = 1;a<=K;a++){
for(int b = 1;b<=K;b++){
for(int c = 1;c<=K;c++){
save_a = a;
save_b = b;
save_c = c;
surp = a%b;
while(surp!=0){
a = b;
b = surp;
surp = a % b ;
}
//bにaとbの最大公約数が入っている
if(b<c){
temp = b;
b = c;
c = temp;
}
surp = b%c;
while(surp!= 0){
b = c;
c = surp;
surp = b%c;
}
//ここでcにb,cの最大公約数が入っている
sum = sum+c;
a = save_a;
b = save_b;
c = save_c;
}
}
}
cout << sum<<'\n';
return 0;
}
実行結果
C:\Users\horis\Desktop>g++ -o gcd gcd.cpp -Wall -Werror C:\Users\horis\Desktop>gcd 2 ← 入力 9 ← 出力 C:\Users\horis\Desktop>gcd 200 ← 入力 10813692 ← 出力
まとめ
ユークリッドの互除法を利用することで、最大公約数を簡単に求められる。また、ユークリッドの互除法自体が、機械的であるのでプログラムによる実装も簡単である。
