两个数的最大公约数c++

两个数的最大公约数可以使用辗转相除法或者枚举法来实现。以下是两种方法的C++代码实现：

辗转相除法：

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a = n, b = m;
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    cout << "最大公约数为：" << a << endl;
    return 0;
}

枚举法：

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int x = n < m ? n : m;
    for (x; x >= 1; x--) {
        if (n % x == 0 && m % x == 0) {
            break;
        }
    }
    cout << "最大公约数为：" << x << endl;
    return 0;
}

相关问题

求两个数的最大公约数C++

在C++中，求两个数的最大公约数（Greatest Common Divisor, GCD）通常可以使用欧几里得算法（Euclidean Algorithm），这是一种递归或者迭代的方式来找到两个数的最大公因数。下面是一个简单的C++函数实现：

#include <iostream>

// 使用辗转相除法计算最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a; // 如果b为零，a就是gcd
    } else {
        return gcd(b, a % b); // 递归地计算a除以b的余数作为新的a，b作为新的b
    }
}

int main() {
    int num1, num2;
    std::cout << "请输入两个数字：";
    std::cin >> num1 >> num2;
    int result = gcd(num1, num2);
    std::cout << "这两个数的最大公约数是：" << result << std::endl;
    return 0;
}

在这个程序中，用户输入两个整数，然后`gcd`函数通过不断取余数直到余数为零，最终返回的结果就是它们的最大公约数。

求两个数的最大公约数c++

方法一：可以想到两个数的最大公约数可能是两个数的min，最小可能是1。所以，可以设最大公约数从min开始进行判断，如果gcd大于1并且不能同时整除m和n，那么就gcd-1，重复判断是否整除。

方法二：欧几里德算法，对于任意两个自然数m和n，用m，n，r分别表示被除数，除数，余数，m和n的最大公约数等于n和r的最大公约数，以下是辗转相除法 求m除以n的余数r当r!=0时，执行第3步;若r==0，则n为最大公约数，算法结束将n的值赋值给m，r的值赋值给n，再求m除以n的余数r转到第2步。

以上是两种求两个数的最大公约数的方法。希望能对您有所帮助。