欧几里得算法，又被称为辗转相除法，用于求两个数的最大公约数。算法如下：
欧几里得算法
// 爱码岛编程
#include <iostream>
using namespace std;
// 辗转相除法计算最大公约数
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a = 48, b = 18;
cout << "最大公约数为：" << gcd(a, b) << endl;
return 0;
}
非递归写法
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
或者使用库函数
__gcd(a, b);