首页 > 最大公约数与最小公倍数的详细讲解及求法-云社区

最大公约数与最小公倍数的详细讲解及求法-云社区

网络收集 2021-04-16 06:55:31
最大公约数的基本概念

能够整除一个整数的整数称为其的约数(如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; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

求最小公倍数 最小公倍数的基本概念:

如果一个数既是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; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

求最小公倍数有没有更简单的方法呢?当然,最小公倍数可以不用先去求最大公约数,这种方法如下:

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; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14

文章来源: blog.csdn.net,作者:sjp11,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/sjp11/article/details/114638502

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

一周热门

查看更多