输入两个正整数，求最大公约数

最大公约数可以使用欧几里得算法来求解，即不断用较小的数去除较大的数，直到两数相等为止，最后的余数即为最大公约数。以下是示例代码：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

其中，a 和 b 分别为输入的两个正整数，返回值为它们的最大公约数。

相关问题

输入两个正整数求最大公约数最小公倍数

最大公约数可以使用辗转相除法或欧几里得算法求解，最小公倍数可以通过最大公约数求解。

辗转相除法：

设两个正整数为a和b，且a>b，用a除以b，得到余数r，若r为，则b即为最大公约数；若r不为，则用b除以r，得到余数r1，若r1为，则r即为最大公约数；若r1不为，则继续用r除以r1，直到余数为为止。

最大公约数：两个正整数a和b的最大公约数为gcd(a,b)。

最小公倍数：两个正整数a和b的最小公倍数为lcm(a,b) = a*b/gcd(a,b)。

例如，输入两个正整数10和15，先求最大公约数，使用辗转相除法，得到：

10÷15=...10

15÷10=1...5

10÷5=2...

因此，gcd(10,15)=5。

再求最小公倍数，使用公式lcm(10,15) = 10*15/5 = 30。

因此，10和15的最大公约数为5，最小公倍数为30。

输入两个正整数求最大公约数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\})$。如果需要求多组数据的最大公约数，可以将代码封装为一个函数，然后在主函数中循环调用即可。