ユーグリッド互除法 - なんだかいろいろウィキ

ユーグリッド互除法とは

最大公約数を求める手法

解法

a>bの整数a bがある
aをbで割り余りをcとする
bをcで割り余りをdとする
cをdで割り余りをeとする
上記を繰り返し余りが0になったら
そのときの割った数が最大公約数
となる。
例）上記のeが0ならば最大公約数はdである

int ugu(int a,int b){
int temp;
int c=a%b;
   while(1){
      temp=b%c;
      if(temp==0) return c;
      c=temp;
   }
}