Ну, а если писать очень кратко, то НОД можно найти так:
int GCD( int a, int b )
{
while( a*b ) a > b ? a %= b : b %= a;
return a+b;
}