欧几里德算法的基本方法是重复应用 m mod n ,直到最后的模值为0 。
基本算法
int gcd(int m, int n)
{
int temp ;
while ( n > 0)
{
temp = m % n ;
m = n ;
n = temp ;
}
return m ;
}
递归写法
int gcd ( int m , int n )
{
return n == 0 ? m : gcd( m%n, n ) ;
}
位运算写法
int gcd(int m,int n)
{
while(n^=m^=n^=m%=n);
return m;
}