求GCD(最大公约数)的算法
程序员文章站
2022-07-13 23:54:10
...
int GCD ( int a , int b) //递归版
{
if ( b != 0 ) return GCD( b, a%b );
return a;
}
int GCD ( int a , int b) //非递归版
{
int c;
while (b)
{
c = a;
a = b;
b = c % a;
}
return a;
}
另一种方法:
若x,y均为偶数,gcd(x,y) = 2 * gcd(x/2,y/2);
若只x均为偶数,gcd(x,y) = gcd(x/2,y);
若只y均为偶数,gcd(x,y) = gcd(x,y/2);
若x,y均为奇数,gcd(x,y) = gcd(y, x- y);(两个奇数相减,必得偶数)
上一篇: GCD求最大公约数
下一篇: 设计模式---外观模式