最大公约数与最小公倍数的详细讲解及求法
·
最大公约数的基本概念
能够整除一个整数的整数称为其的约数(如5是10约数);能够被一个整数整除的整数称为其的倍数(如10是5的倍数);如果一个数既是数A的约数,又是数B的约数,称为A,B的公约数,A,B的公约数中最大的一个(可以包括AB自身)称为AB的最大公约数。
辗转相除法求最大公约数
辗转相除法的基本做法
用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数
int main()
{
int a = 0;
int b = 0;
int c = 0;
scanf("%d%d", &a, &b);
while (b)
{
c = a%b;
a = b;
b = c;
}
printf("%d\n", a);
return 0;
}
求最小公倍数
最小公倍数的基本概念:
如果一个数既是a又是b的倍数,那么我们就把这个数叫着a和b的公倍数,如果这个数在a b的所有公倍数里为最小,那这个数就是最小公倍数。
利用最大公约数求最小公倍数
已知a,b最大公约数为i,最小公倍数为j,则有公式为a*b=最大公约数i * 最小公倍数j
所以可以用该公式求出最小公倍数
int main()
{
int a = 0;
int b = 0;
int c = 0;
scanf("%d%d", &a, &b);
int i = a;
//将a,b的值保存在i和j
int j = b;
while (b)
{
c = a%b;
a = b;
b = c;
}
printf("最大公约数=%d\n", a);
//求最小公倍数
//最大公约数乘*最小公倍数=两个数的乘积i*j
int ret = (i*j) / a;
printf("最小公倍数=%d\n", ret);
return 0;
}
求最小公倍数有没有更简单的方法呢?当然,最小公倍数可以不用先去求最大公约数,这种方法如下:
int main()
{
int a = 0;
int b = 0;
scanf("%d%d", &a, &b);
int i = 1;
//24 16
while ((a*i) % b)
{
i++;
}
printf("%d\n", a*i);
return 0;
}
更多推荐
已为社区贡献6条内容
所有评论(0)