用c++求两个数的最大公约数
时间: 2024-02-04 15:09:04 浏览: 27
以下是两种用C++求两个数的最大公约数的方法:
方法一:暴力法
```cpp
#include <iostream>
using namespace std;
int main() {
int m, n, gcd;
cin >> m >> n;
gcd = m > n ? n : m;
while (gcd > 1 && (m % gcd != 0 || n % gcd != 0)) {
gcd--;
}
cout << gcd << endl;
return 0;
}
```
方法二:欧几里德算法(辗转相除法)
```cpp
#include <iostream>
using namespace std;
int main() {
int m, n;
cin >> m >> n; int r = m % n;
while (r != 0) {
m = n;
n = r;
r = m % n;
}
cout << "gcd=" << n << endl;
return 0;
}
```
相关问题
用c++求两个数的最大公约数和最小公倍数
以下是用C++求两个数的最大公约数和最小公倍数的代码和解释:
```c++
#include <iostream>
using namespace std;
int main() {
int m, n, gys, gbs, i, j;
cout << "请输入两个正整数m和n:" << endl;
cin >> m >> n;
// 求最大公约数
for (i = 1; i <= m && i <= n; i++) {
if ((m % i == 0) && (n % i == 0)) {
gys = i;
}
}
cout << "m与n的最大公约数是:" << gys << endl;
// 求最小公倍数
for (j = 1;; j++) {
if ((j % m == 0) && (j % n == 0)) {
gbs = j;
cout << "m与n的最小公倍数是:" << gbs << endl;
break;
// 如果没有break,程序将无限循环;如果break放到if的花括号外面,将不会输出结果,因为第一次判断后,程序就已经跳出循环了。
}
}
return 0;
}
```
解释:
1. 首先,我们定义了4个变量:m、n、gys、gbs,其中m和n是用户输入的两个正整数,gys和gbs分别表示最大公约数和最小公倍数。
2. 然后,我们使用for循环来求最大公约数。从1开始循环,一直到m和n中较小的那个数为止,每次判断i是否是m和n的公约数,如果是,就将i赋值给gys。
3. 最后,我们使用另一个for循环来求最小公倍数。从1开始循环,每次判断j是否是m和n的公倍数,如果是,就将j赋值给gbs,并输出结果,然后使用break语句跳出循环。
用C++语言求两个数的最大公约数
可以使用辗转相除法来求两个数的最大公约数,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` 函数使用递归的方式来求最大公约数,如果 `b` 等于 0,那么 `a` 就是最大公约数,否则递归调用 `gcd(b, a % b)`。在 `main` 函数中,先读入两个数,然后调用 `gcd` 函数求它们的最大公约数,并输出结果。