C++辗转相除法求最大公约数

C语言中，使用辗转相除法求最大公约数的方法有两种实现方式。一种是递归实现，另一种是循环实现。

递归实现的代码如下：

int gcd(int a, int b) {
    if (b > a)
        return gcd(b, a);
    int remind = a % b;
    if (remind == 0)
        return b;
    else
        return gcd(b, remind);
}

循环实现的代码如下：

int gcd(int a, int b) {
    if (b > a)
        return gcd(b, a);
    int remind = 1;
    while (remind) {
        remind = a % b;
        a = b;
        b = remind;
    }
    return a;
}

这两种方法的原理都是通过辗转相除的过程，即用较大的数除以较小的数得到余数，再用较小的数除以余数以此循环，直到最后余数为零。最后一次除的数即为最大公约数。

所以通过调用这两个方法，可以求出两个正整数的最大公约数。

相关问题

编写C++用辗转相除法求最大公约数

下面是用 C 语言编写的辗转相除法求最大公约数的代码：

#include <stdio.h>

int gcd(int a, int b) {
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main() {
    int a, b;
    printf("请输入两个正整数：");
    scanf("%d %d", &a, &b);
    printf("它们的最大公约数是：%d\n", gcd(a, b));
    return 0;
}

代码中的 `gcd` 函数用于实现辗转相除法求最大公约数，其中 `a` 和 `b` 分别表示两个正整数。在函数中，首先计算 `a` 对 `b` 取模的结果 `r`，然后利用循环不断将 `b` 赋值给 `a`，`r` 赋值给 `b`，并重新计算 `r` 的值，直到 `r` 等于 0，此时最大公约数即为 `b`。

在 `main` 函数中，首先通过 `scanf` 函数获取用户输入的两个正整数，然后调用 `gcd` 函数求它们的最大公约数，并通过 `printf` 函数输出结果。

c++用辗转相除法求最大公约数和最小公倍数

在 C++ 中，可以使用欧几里得算法（也称为辗转相除法或更相减损术）来求两个整数的最大公约数（Greatest Common Divisor, GCD）。这个算法基于这样一个原理：两个整数的最大公约数等于其中较小的那个数和两数余数的最大公约数。

以下是简单的 C++ 代码示例：

#include <iostream>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 使用上面的gcd函数计算最小公倍数(LCM)
int lcm(int a, int b) {
    int temp = gcd(a, b);
    return (a * b) / temp;
}

int main() {
    int num1, num2;
    std::cout << "请输入两个整数：";
    std::cin >> num1 >> num2;

    std::cout << "最大公约数(GCD)为：" << gcd(num1, num2) << "\n";
    std::cout << "最小公倍数(LCM)为：" << lcm(num1, num2) << "\n";

    return 0;
}

在这个例子中，`gcd` 函数递归地应用辗转相除法则，直到找到 `b` 等于 0 的情况。然后，`lcm` 函数利用 `gcd` 计算结果和原始两个数乘积除以 `gcd` 的值，即得到最小公倍数。