用辗转相除法求任意两个正整数的最大公约数的C语言编程
时间: 2023-06-05 21:04:34 浏览: 98
很高兴为您解答问题。以下是使用辗转相除法求任意两个正整数的最大公约数的 C 语言代码:
```c
#include <stdio.h>
int gcd(int x, int y) {
int r;
while (y != 0) {
r = x % y;
x = y;
y = r;
}
return x;
}
int main() {
int a, b;
printf("请输入两个正整数:");
scanf("%d%d", &a, &b);
int result = gcd(a, b);
printf("这两个数的最大公约数是:%d", result);
return 0;
}
```
可以看出,这段代码中使用了辗转相除法计算最大公约数。对于输入的两个正整数 a 和 b,首先计算它们的余数 r = a % b,然后让 a = b,b = r,重复这个过程直到得到的余数为 0,此时 a 的值即为这两个数的最大公约数。
希望这个回答能够帮助到您!
相关问题
c语言用辗转相除法求出两个正整数的最大公约数和最小公倍数
最大公约数和最小公倍数的求法如下:
最大公约数(GCD):辗转相除法,也叫欧几里得算法,是求两个正整数的最大公约数的常用方法。
最小公倍数(LCM):两个正整数a和b的积等于它们的最大公约数(GCD)和最小公倍数(LCM)的积,即a*b=GCD(a,b)*LCM(a,b),因此可以通过最大公约数来求最小公倍数。
以下是C语言代码实现:
```c
#include <stdio.h>
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 num1, num2;
printf("Enter two positive integers: ");
scanf("%d %d", &num1, &num2);
printf("GCD(%d, %d) = %d\n", num1, num2, gcd(num1, num2));
printf("LCM(%d, %d) = %d\n", num1, num2, lcm(num1, num2));
return 0;
}
```
代码解释:
- 定义函数gcd来求最大公约数,使用递归实现辗转相除法,当b为0时,a即为最大公约数。
- 定义函数lcm来求最小公倍数,使用a*b/GCD(a,b)的公式来计算。
- 在main函数中,先输入两个正整数,然后调用gcd和lcm函数分别求出它们的最大公约数和最小公倍数,并输出结果。
c语言 辗转相除法求两个正整数的最大公约数和最小公倍数。
辗转相除法是求两个正整数的最大公约数的一种常用方法,同时也可以用来求最小公倍数。以下是使用C语言实现辗转相除法求两个正整数的最大公约数和最小公倍数的代码:
```
#include <stdio.h>
int main() {
int m, n, t, e, gcd, lcm;
// 输入两个数
printf("请输入两个正整数:\n"); scanf("%d%d", &m, &n);
t = m * n;
// 为保证大的除小的,如果m<n,则做交换
if (m < n) {
int temp;
temp = m;
m = n;
n = temp;
}
// 辗转相除法求最大公约数
e = m % n;
while (e != 0) {
m = n;
n = e;
e = m % n;
}
gcd = n;
lcm = t / gcd;
printf("它们的最大公约数是: %d\n", gcd);
printf("它们的最小公倍数是: %d\n", lcm);
return 0;
}
```
在这个代码中,我们首先输入了两个正整数m和n,然后计算它们的乘积t。为了保证大的除小的,我们对m和n进行了交换。接着,我们使用辗转相除法求出了它们的最大公约数gcd,并根据最大公约数求出了最小公倍数lcm。最后,我们输出了它们的最大公约数和最小公倍数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)