【C】C语言三种算法求解最大公约数与最小公倍数

博主： Fivk
发布时间：2020 年 11 月 06 日
1382 次浏览
2614字数
分类： C/C++

最大公约数与最小公倍数的求解是很多初学C的人所面临的一道问题。当然这道问题并不难解答，也有很多人已经写过相关的博客，我在此书写此篇博客，一是为了让自己能够夯实基础，另外就是希望能够帮到和我一样的初学者。

当然，在写这篇博客之前，我已经做过相关资料的调查，可能读者会发现此篇博客会与其他人的博客有所重复，但是，我保证绝未抄袭。好了，进入正题！

问题：请从键盘上输入两个数值 x，y，请用C语言求出这两个数值的最大公约数与最小公倍数。

首先，我们要想解决这道问题，就要了解什么是最大公约数与最小公倍数。

最大公因数；也称最大[公约数](http://baike.baidu.com/item/%E5%85%AC%E7%BA%A6%E6%95%B0)、最大公[因子](http://baike.baidu.com/item/%E5%9B%A0%E5%AD%90)，指两个或多个[整数](http://baike.baidu.com/item/%E6%95%B4%E6%95%B0)共有[约数](http://baike.baidu.com/item/%E7%BA%A6%E6%95%B0)中最大的一个。----来源百度百科

最小公倍数：两个或多个[整数](http://baike.baidu.com/item/%E6%95%B4%E6%95%B0)公有的倍数叫做它们的公倍数。----来源百度百科

了解了其含义，接下来就是构思算法，通常而言，求解最大公约数有三种算法，而最小公倍数的求解，我们可以很容易的推断出，最小公倍数等于两个数值的乘积除以这两个数值的最大公约数。那么接下来的算法我将在此一一进行列举和解释。

1.辗转相除法：

又名[欧几里德算法](http://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%B7%E7%AE%97%E6%B3%95)（Euclidean algorithm），它是已知最古老的算法， 其可追溯至公元前300年前。 ----来源百度百科

辗转：望文生义，就是翻来覆去。相除就很好理解了，就是进行除法运算。

辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

假设两数为 x，y。

先令 z = x % y ;

之后 y 赋给 x 即令  x = y ;

再将 z 赋给 y 即令  y = z；

辗转相减，其终止条件为：y 等于0时。

代码如下：

```
#include<stdio.h>
int main()
{
int x, y, z, m, n;
printf("请输入两个数：");
scanf_s("%d%d", &x, &y);
m = x, n = y;
while (y != 0)
{
z = x%y;
x = y;
y = z;
}
printf("最大公约数是: %d\n", x);
printf("最小公倍数是: %d\n", m*n / x);
system("pause");
return 0;
}
```

2.辗转相减法：

即[尼考曼彻斯法](http://baike.baidu.com/item/%E5%B0%BC%E8%80%83%E6%9B%BC%E5%BD%BB%E6%96%AF%E6%B3%95)，其特色是做一系列减法，从而求得[最大公约数](http://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0)。----来源百度百科

辗转相减法即通过对两数的不断减法运算。

假设两数为 x, y。

当 x > y 时，令 x = x - y;

反之，则令 y = y - x;

之后一直辗转相减，直至 x = y 时，终止。

代码如下：

```
#include<stdio.h>
int main()
{
	int x, y, m, n;
	printf("请输入两个数：");
	scanf_s("%d%d", &x, &y);
	m = x, n = y;
	while (x!=y)
	{
		if (x>y)
			x = x-y;
		else
			y = y-x;
	}
	printf("最大公约数是: %d\n", x);
	printf("最小公倍数是: %d\n", m*n / x);
	system("pause");
	return 0;
}
```

3.穷举法：

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。----来源百度百科

穷举法又称枚举法，通过对数值范围内的所有数字进行检验，得出其结果。

代码如下：

```
#include<stdio.h>
int main()
{
	int x, y, i, m, n;
	printf("请输入两个数：");
	scanf_s("%d%d", &x, &y);
	m = x, n = y;
	for (i = 1; i <= x; i++)
	{
		if (x%i == 0 && y%i == 0)
			break;
	}
	for (i = x; i > 0; i--)
	{
		if (x%i == 0 && y%i == 0)
			break;
	}
	printf("最大公约数是: %d\n", i);
	printf("最小公倍数是: %d\n", m*n / i);
	system("pause");
	return 0;
}
```

以上即为求解最大公约数与最小公倍数的三种算法，如有纰漏，还请各位不吝赐教。

`<div class="preview">
<div class="post-inser post box-shadow-wrap-normal">
<a href="https://blog.csdn.net/Zhang_1218/article/details/73196314" target="_blank" class="post_inser_a no-external-link no-underline-link">
<div class="inner-image bg" style="background-image: url(https://profile.csdnimg.cn/D/F/0/3_zhang_1218.jpg);background-size: cover;"></div>

<div class="inner-content" >
<p class="inser-title">@本文转自</p>
<div class="inster-summary text-muted">
露航 
</div>
</div>
</a>

</div>

</div>`

最后修改：2020 年 11 月 07 日

如果觉得我的文章对你有用，请随意赞赏

【C】C语言三种算法求解最大公约数与最小公倍数

Fivk • 2020 年 11 月 06 日

问题：请从键盘上输入两个数值 x，y，请用C语言求出这两个数值的最大公约数与最小公倍数。

首先，我们要想解决这道问题，就要了解什么是最大公约数与最小公倍数。

最小公倍数：两个或多个[整数](http://baike.baidu.com/item/%E6%95%B4%E6%95%B0)公有的倍数叫做它们的公倍数。----来源百度百科

1.辗转相除法：

辗转：望文生义，就是翻来覆去。相除就很好理解了，就是进行除法运算。

辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

假设两数为 x，y。

先令 z = x % y ;

之后 y 赋给 x 即令  x = y ;

再将 z 赋给 y 即令  y = z；

辗转相减，其终止条件为：y 等于0时。

代码如下：

2.辗转相减法：

辗转相减法即通过对两数的不断减法运算。

假设两数为 x, y。

当 x > y 时，令 x = x - y;

反之，则令 y = y - x;

之后一直辗转相减，直至 x = y 时，终止。

代码如下：

3.穷举法：

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。----来源百度百科

穷举法又称枚举法，通过对数值范围内的所有数字进行检验，得出其结果。

代码如下：

以上即为求解最大公约数与最小公倍数的三种算法，如有纰漏，还请各位不吝赐教。

【C】C语言三种算法求解最大公约数与最小公倍数

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【知识总结】@mapper和@repository区别

【开发技巧】Vue2中如何优雅地实现dialog的封装

【踩坑日志】ServiceAuthFeign#getAllowedClient(String,String) failed and no fallback available.

【微服务】elasticsearch分布式搜索引擎（下）

【Redis】SpringBoot项目Redis哨兵集群和单节点自适应

【C】C语言三种算法求解最大公约数与最小公倍数