输入两个正整数,求最大公约数
时间: 2023-04-11 21:02:30 浏览: 244
最大公约数可以使用欧几里得算法来求解,即不断用较小的数去除较大的数,直到两数相等为止,最后的余数即为最大公约数。以下是示例代码:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
```
其中,a 和 b 分别为输入的两个正整数,返回值为它们的最大公约数。
相关问题
输入两个正整数求最大公约数C++
以下是 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
int main() {
int num1, num2;
cout << "请输入两个正整数:" << endl;
cin >> num1 >> num2;
// 求最大公约数
int gcd = 1;
for (int i = 1; i <= num1 && i <= num2; ++i) {
if (num1 % i == 0 && num2 % i == 0) {
gcd = i;
}
}
// 输出结果
cout << num1 << "和" << num2 << "的最大公约数为:" << gcd << endl;
return 0;
}
```
该程序通过暴力枚举的方式找到两个数的最大公约数,时间复杂度为 $O(\min\{num1, num2\})$。如果需要求多组数据的最大公约数,可以将代码封装为一个函数,然后在主函数中循环调用即可。
python输入两个正整数求最大公约数
5和7都是正整数,可以用以下代码进行求解:
```
a = int(input("请输入第一个整数:"))
b = int(input("请输入第二个整数:"))
if a > b:
max_gcd = a
else:
max_gcd = b
while True:
if max_gcd % a == 0 and max_gcd % b == 0:
break
max_gcd += 1
print("最大公约数为:", max_gcd)
```
阅读全文