C语言求最大公约数的方法有哪些

c语言

小亿

236

2023-08-12 01:28:38

栏目: 编程语言

C语言求最大公约数的方法有以下几种：

辗转相除法：即用较大的数除以较小的数，然后用余数代替较大的数，再用较小的数除以余数，直到余数为0为止，此时较小的数即为最大公约数。

int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a%b);
}

更相减损法：即用较大的数减去较小的数，然后用差值代替较大的数，再用较小的数减去差值，直到两个数相等为止，此时相等的数即为最大公约数。

int gcd(int a, int b) {
if (a == b) {
return a;
}
if (a > b) {
return gcd(a-b, b);
}
return gcd(a, b-a);
}

移位法：当a和b都是偶数时，2是它们的公约数，然后将a和b都右移1位，再继续求最大公约数，直到其中一个为0，此时另一个数即为最大公约数的2的幂倍。

int gcd(int a, int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
if ((a&1) == 0 && (b&1) == 0) {
return 2 * gcd(a>>1, b>>1);
}
if ((a&1) == 0) {
return gcd(a>>1, b);
}
if ((b&1) == 0) {
return gcd(a, b>>1);
}
if (a > b) {
return gcd(a-b, b);
}
return gcd(a, b-a);
}

这些方法都可以用于求两个整数的最大公约数。

C语言求最大公约数的方法有哪些

最新问答

相关标签