请给出欧几里得算法的c++代码
时间: 2024-09-10 22:17:48 浏览: 49
欧几里得算法,也称为辗转相除法,用于求两个正整数的最大公约数(GCD)。以下是使用C++实现的一个简单版本:
```cpp
#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++实现的扩展欧几里得算法的示例代码:
```cpp
#include <iostream>
// 扩展欧几里得算法
int extendedGCD(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int gcd = extendedGCD(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}
// 测试代码
int main() {
int a = 56;
int b = 15;
int x, y;
int gcd = extendedGCD(a, b, x, y);
std::cout << "GCD(" << a << ", " << b << ") = " << gcd << std::endl;
std::cout << "贝祖等式: " << gcd << " = " << x << "*" << a << " + " << y << "*" << b << std::endl;
return 0;
}
```
运行此代码,将输出:
```
GCD(56, 15) = 1
贝祖等式: 1 = -4*56 + 15*15
```
这个例子演示了如何使用扩展欧几里得算法计算56和15的最大公约数,并输出它们的贝祖等式。
扩展欧几里得算法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 ]
阅读全文