请给出欧几里得算法的c++代码

欧几里得算法，也称为辗转相除法，用于求两个正整数的最大公约数（GCD）。以下是使用C++实现的一个简单版本：

#include <iostream>

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

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

    if (num1 < 0 || num2 < 0)
        std::cout << "输入的数字应该是非负的。\n";
    else
        std::cout << "两数的最大公约数是: " << gcd(num1, num2) << "\n";

    return 0;
}

在这个程序中，`gcd`函数递归地计算两个数的余数，直到余数为零，此时前一个数就是最大公约数。用户可以从主函数中输入两个整数，然后调用`gcd`函数来获取它们的最大公约数。

相关问题

欧几里得算法c++实现

欧几里得算法，也称辗转相除法，是求两个正整数的最大公约数的算法。其基本思想是：用较大的数除以较小的数，再用除数除以出现的余数（第一次出现的余数即为两数的最大公约数），再用新的余数去除除数，如此反复，直到余数为零为止。

以下是 C 语言实现欧几里得算法的示例代码：

#include <stdio.h>

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

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

首先定义了一个 `gcd()` 函数，函数参数为两个正整数 `a` 和 `b`，返回值为它们的最大公约数。在函数内部，先判断 `b` 是否等于 0，如果是就直接返回 `a`，否则就递归调用 `gcd()` 函数，将 `b` 和 `a % b` 作为参数传入。

在 `main()` 函数中，先输入两个正整数 `a` 和 `b`，然后调用 `gcd()` 函数求它们的最大公约数，并输出结果。

扩展欧几里得算法c++

扩展欧几里得算法是用来解决线性同余方程的一种方法。它可以找到整数x和整数y，使得ax + by = gcd(a, b)成立。这个算法通过递归的方式，不断地进行辗转相除，直到找到最大公约数。在每一步中，我们更新x和y的值，使得等式成立。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [扩展欧几里得算法 C++ （ 原来还可以这样做 tql ）](https://blog.csdn.net/qq_51277605/article/details/118032597)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 50%"]
- *3* [【算法学习】扩展欧几里得算法详解及C++代码实现](https://blog.csdn.net/u014117943/article/details/108428551)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]