>>784
int gcd2(int x, int y){
int i, tmp;
if(x > y){
tmp=x;
x=y;
y=tmp;
}
for(i = x; i > 1; i --){
if((x % i == 0) && (y % i == 0)){
return i;
}
}
}

ロジック:(2数x,yのうち小さい方-1)~2までカウントダウンして、x,y両方を割り切れた最初の数が最大公約数。
所用時間:手元のPCで30秒位。