欧几里得算法c++实现
时间: 2023-09-25 21:16:14 浏览: 37
欧几里得算法,也称辗转相除法,是求两个正整数的最大公约数的算法。其基本思想是:用较大的数除以较小的数,再用除数除以出现的余数(第一次出现的余数即为两数的最大公约数),再用新的余数去除除数,如此反复,直到余数为零为止。
以下是 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++中实现欧几里得算法
欧几里得算法,也称为辗转相除法,用于计算两个非负整数的最大公约数(GCD)。在C++中,可以使用递归或迭代两种方法来实现欧几里得算法。
1. 递归实现:
```cpp
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
```
在这个实现中,如果b等于0,则a就是最大公约数。否则,我们递归地调用`gcd(b, a % b)`来求解a和b的最大公约数。
2. 迭代实现:
```cpp
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
```
在这个实现中,我们使用一个循环来迭代地计算最大公约数。在每一轮迭代中,我们更新a为b,b为a除以b的余数。
你可以调用`gcd(a, b)`函数来计算a和b的最大公约数。