求两个正整数的最大公约数和最小公倍数c++
时间: 2023-05-03 14:00:40 浏览: 76
在C++中,求两个整数的最大公约数和最小公倍数可以使用以下方法:
1.最大公约数:使用辗转相除法,即将两个数轮流相除取余数,直到余数为0,最后被除数即为最大公约数。
2.最小公倍数:先求出最大公约数,然后将两个数相乘,最后除以最大公约数即可得到最小公倍数。
相关问题
c++怎么求两个正整数的最大公约数和最小公倍数
求两个正整数a和b的最大公约数和最小公倍数的方法如下:
1. 求最大公约数:
最大公约数可以用辗转相除法求解,即:
设a、b为两个正整数,且a>b,则有:
a % b = c
若c = 0,则b为最大公约数;否则,将b赋值为c,再将a赋值为原来的b,重复上述操作,直到c=0。
例如,求30和45的最大公约数:
30 % 45 = 30
45 % 30 = 15
30 % 15 = 0
因此,最大公约数为15。
2. 求最小公倍数:
最小公倍数可以用公式求解,即:
最小公倍数 = a × b / 最大公约数
例如,求30和45的最小公倍数:
最大公约数为15,因此最小公倍数为30 × 45 / 15 = 90。
c++求两个正整数的最大公约数和最小公倍数
可以使用辗转相除法求两个正整数的最大公约数,公式如下:
```cpp
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
```
其中,参数 a 和 b 分别表示需要求最大公约数的两个正整数。
而最小公倍数可以通过最大公约数求得,公式如下:
```cpp
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
```
同样的,参数 a 和 b 分别为需要求最小公倍数的两个正整数。
完整代码如下:
```cpp
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int a, b;
cout << "请输入两个正整数:" << endl;
cin >> a >> b;
cout << "它们的最大公约数为:" << gcd(a, b) << endl;
cout << "它们的最小公倍数为:" << lcm(a, b) << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)