前言
我们在C语言的学习中,经常会遇到这样一些数学题目,良好掌握这些题目有利于我们理解和学习C语言,话不多说,直接进入主题
什么是最大公约数和最小公倍数
最大公约数:
首先我们举个例子,比如12 和16,12的约数有(1,2 ,3,4,6,12),16的约数有(1,2,4,8,16)公约数就是两个数共同的约数,(1,2,4)而公约数中最大的就是最大公约数。
最小公倍数
我们同样举个例子,比如12和16,我们将163=48,124=48,这是两个数第一次有倍数相等关系,就叫48是最小公倍数
最大公约数与最小公倍数的公式
最大公约数 —— Greatest Common Divisor(GCD)
最小公倍数 —— Leatest Common Multiple(LCM)
假设a和b是我们已知的数,那么 就存在一个公式。
公式展示
a ∗ b = G C D ∗ L C M a*b=GCD*LCM a∗b=GCD∗LCM
这与我们的路程公式很相似,我们可以类比记忆,路程=速度*时间
所以我们只要求出其中的一个就行,求出GCD 就可以通过公式求出LCM,
求出LCM就可以通过公式求出GCD。
求最大公约数方法
方法一:暴力穷举法
细节讲解: 我们知道最大公约数是约数中能同时整除两数,并且是最先整除的,那我们就可以一个一个试。我们可以将l两个数中小的那个赋给tmp,为什么呢?因为我们找最大公倍数时最大也不会超过a,b两个数中最小的那个。
比如16 和12 ,我们肯定是从12往下找,而不是还要在16~12之间浪费时间。 我们来看看代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int tmp = a > b ? b : a;
while (1)
{
if (a % tmp == 0 && b % tmp == 0)
{
printf("最大公约数是%d", tmp);
break;
}
else
tmp--;
}
return 0;
}
方法二:辗转相除法
在数学中,辗转相除法,又称欧几里得算法(Euclidean algorithm),是求取最大公约数的一种算法。辗转相除法首次出现于欧几里得的《几何原本》中的第Ⅶ卷,书中的命题ⅰ和命题ⅱ所描述的就是辗转相除法,而在中国,辗转相除法最早出现在《九章算法》中。可以说这是一个非常经典的方法
我们来看流程图
解析:如果我们有a,b a = 24 b = 18 ,我们先让 24 % 18 = 6 ,
接下来我们让 18 % 6 = 0 ;刚好符合我们流程图中蓝色框框的条件,这样就能确定 6 就是最大公倍数。如果是18 % 24 呢?
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
while (1)
{
int c = a % b;
if (0 == a % b)
{
printf("%d就是最大公约数", b);
break;
}
else
{
a = b ;
b = c;
}
}
return 0;
}
方法三:更相减损术
《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数
流程图:
用更相减损术求98与63的最大公约数。
我们只要跟着流程图走,然后一直改变 a 和 b 的值然后直至a b 相等就行,a b 相等时的那个数就是最大公倍数,下面给出代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
while (1)
{
if (a == b)
{
printf("最大公倍数是%d", a);
break;
}
if (a > b)
{
a = a - b;
}
if (b > a)
{
b = b - a;
}
}
return 0;
}
求最小公倍数的方法
方法一:公式法
a ∗ b = G C D ∗ L C M a*b=GCD*LCM a∗b=GCD∗LCM
所以我们只要求出其中的一个就行,求出GCD 就可以通过公式求出LCM,
我们上面已经介绍了三种求GCD的方法,直接用公式也是可以的。
方法二:暴力穷举法
我们知道最小公倍数就是能够同时整除我们已知的两个数的数,而且我们可以从两个数中更大的开始,比如说求45和30的最小公倍数。
我们肯定是从45 往上找。
由于方法比较暴力我们就直接看代码吧!
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int c = a > b ? a : b;
while (1)
{
if (0 == c % a && 0 == c % b)
{
printf("最小公倍数是%d", c);
break;
}
c++;
}
return 0;
}
方法三:叠乘法
方法讲解:
已知两个数的公倍数一定与这两个数存在倍数关系,那么求解最小公倍数我们就可以将其中一个数依次扩大1倍、2倍、3倍……直到出现第一个扩大n倍的数可以同时整除这两个数,这个数就是最小公倍数。
计算36和270的最小公倍数
我们直接给出代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int i = 1;
while (a * i % b != 0)
{
i++;
}
printf("最小公倍数是%d", a * i);
return 0;
}
最后总结
通过这篇博客我们知道了求最大公约数和最小公倍数的许多方法,当然不止这些方法,但是我觉得这些应该够用一段时间了。我是一个博客新手,本文若是有笔误之处,请大家多多指出。最后写博客是一件很辛苦但是很有成就感的一件事情。文章来源:https://www.toymoban.com/news/detail-761810.html
这篇文章到这里就结束了,如果有帮到你就请点个赞吧。我的博客是不添加水印的,大家也可以用里面的图片。最后就麻烦用你的小手点个赞吧,哈哈Thanks♪(・ω・)ノ
文章来源地址https://www.toymoban.com/news/detail-761810.html
到了这里,关于【C语言】一篇博客带你弄懂最大公约数和最小公倍数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!