유클리드 호제법(최대 공약수)

1071과 1029의 최대공약수를 구하면,
1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.
78696과 19332의 최대공약수를 구하면,
    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108 
      180 ＝ 108×1 + 72     
      108 ＝ 72×1 ＋ 36 
       72 ＝ 36×2
따라서, 최대공약수는 36이다.

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

#include <stdio.h>

int main(){

int x, y;

scanf("%d %d", &x, &y);

printf("%d", gcd(x, y));

}

int gcd(int a, int b)

{

return b ? gcd(b, a%b) : a;

}