ユークリッドの互除法

これ以上でもこれ以下でもなく、普通にユークリッドの互除法(Euclidean Algorithm)で最大公約数(greatest common divisor)を求めるだけ

int gcd(int a, int b){

  int c;

  if(a<b){

    a+=b;

    b=a-b;

    a-=b;

  }

  while(b!=0){

    c=a%b;

    a=b;

    b=c;

  }

  return a;

}