求两个正整数的最大公约数和最小公倍数c++
时间: 2023-06-13 20:09:15 浏览: 116
可以使用辗转相除法来求两个正整数的最大公约数,使用公式:
gcd(a, b) = gcd(b, a % b)
其中,a 和 b 分别为两个正整数,% 表示取模运算,gcd 表示最大公约数。
代码实现如下:
```c++
#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;
}
```
输入:
```
10 15
```
输出:
```
最大公约数:5
最小公倍数:30
```
相关问题
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;
}
```
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。
阅读全文