计算两个数的最大公约数的函数
时间: 2024-06-13 09:05:29 浏览: 11
题目要求实现一个计算两个数的最大公约数的简单函数,可以使用更相减损法或辗转相除法或Stein算法来实现。更相减损法是中国古代的一种求最大公约数的算法,辗转相除法是欧几里得提出的一种求最大公约数的算法,而Stein算法是结合了辗转相除法和更相减损法的优势以及移位运算的一种求最大公约数的算法。下面是三种方法的代码实现:
方法1:更相减损法
```
int gcd(int a, int b) {
if (a == b) {
return a;
}
if (a < b) {
swap(a, b);
}
return gcd(a - b, b);
}
```
方法2:辗转相除法
```
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
```
方法3:Stein算法
```
int gcd(int a, int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
int p = 0;
while ((a & 1) == 0 && (b & 1) == 0) {
a >>= 1;
b >>= 1;
p++;
}
while ((a & 1) == 0) {
a >>= 1;
}
while ((b & 1) == 0) {
b >>= 1;
}
while (a != b) {
if (a > b) {
swap(a, b);
}
b -= a;
do {
b >>= 1;
} while ((b & 1) == 0);
}
return a << p;
}
```