#创作计划#AI都不知道的最大公约数做法
2026-03-14 16:40:11
发布于：广东
5阅读
0回复
0点赞
众所周知
求最大公约数有2种做法：
1.辗转相除法（欧几里得算法）
这是效率最高、最常用的方法，核心思想是：gcd(a, b) = gcd(b, a % b)，直到余数为 0，此时的被除数就是最大公约数。
#include <iostream>
using namespace std;
// 递归实现欧几里得算法
int gcd_recursive(int a, int b) {
// 确保输入为非负数（最大公约数只考虑正整数）
a = abs(a);
b = abs(b);
// 递归终止条件：余数为0时，返回当前的被除数
if (b == 0) {
return a;
}
// 递归调用：gcd(a,b) = gcd(b, a%b)
return gcd_recursive(b, a % b);
}
// 非递归实现欧几里得算法（更高效，避免递归栈开销）
int gcd_iterative(int a, int b) {
// 确保输入为非负数
a = abs(a);
b = abs(b);
// 循环直到余数为0
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2;
cout << "请输入两个整数：";
cin >> num1 >> num2;
// 调用递归版本
int result1 = gcd_recursive(num1, num2);
cout << "递归版计算结果：" << num1 << " 和 " << num2 << " 的最大公约数是：" << result1 << endl;
// 调用非递归版本
int result2 = gcd_iterative(num1, num2);
cout << "非递归版计算结果：" << num1 << " 和 " << num2 << " 的最大公约数是：" << result2 << endl;
return 0;
}
豆包AI生成
2.枚举法
核心思想是：从两个数中较小的数开始，向下枚举，第一个能同时整除两个数的数就是最大公约数。
#include <iostream>
#include <algorithm> // 用于min函数
using namespace std;
int gcd_enumerate(int a, int b) {
// 确保输入为非负数
a = abs(a);
b = abs(b);
// 处理其中一个数为0的情况（0和n的最大公约数是n）
if (a == 0) return b;
if (b == 0) return a;
// 从较小的数开始向下枚举
int min_num = min(a, b);
for (int i = min_num; i >= 1; --i) {
// 能同时整除a和b，就是最大公约数
if (a % i == 0 && b % i == 0) {
return i;
}
}
return 1; // 所有正整数都能被1整除
}
int main() {
int num1, num2;
cout << "请输入两个整数：";
cin >> num1 >> num2;
int result = gcd_enumerate(num1, num2);
cout << num1 << " 和 " << num2 << " 的最大公约数是：" << result << endl;
return 0;
}
豆包AI生成
但是
有一种方法
连AI都不知道
↓ ↓ ↓ ↓ ↓
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
cout << __gcd(a, b);
return 0;
}
直接邪修好吧
__gcd()是C++自带函数
记得点赞！！！
这里空空如也
有帮助，赞一个