欧几里得算法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 ]

连续整数检测算法和欧几里得算法c++

连续整数检测算法通常用于检查一段给定的数字序列中是否存在连续的整数序列，例如 [5, 6, 7, 8, 9] 或者 [10, 11, 12, 13, 14]。这种算法可以通过简单的遍历和比较来实现。下面是一个简单的C++示例：

#include <iostream>
#include <vector>

bool isContinuous(const std::vector<int>& numbers) {
    if (numbers.empty()) {
        return false;
    }

    int prev = numbers[0];
    for (int i = 1; i < numbers.size(); ++i) {
        if (numbers[i] != prev + 1) {
            return false;
        }
        prev = numbers[i];
    }
    return true;
}

int main() {
    std::vector<int> sequence = {5, 6, 7, 8, 9};
    if (isContinuous(sequence)) {
        std::cout << "Sequence is continuous." << std::endl;
    } else {
        std::cout << "Sequence is not continuous." << std::endl;
    }

    return 0;
}

这个程序首先检查序列是否为空，然后通过逐个比较元素之间的差值是否为1，判断是否有连续整数。

欧几里得算法（Euclidean Algorithm），也称辗转相除法，用于求两个正整数的最大公约数（GCD）。其基本思想是不断将较大的数除以较小的数，直到余数为零，此时较小的数就是最大公约数。以下是C++实现：

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

int main() {
    int num1 = 48, num2 = 18;
    int result = gcd(num1, num2);
    std::cout << "The GCD of " << num1 << " and " << num2 << " is: " << result << std::endl;

    return 0;
}