sever2012做网站,做网站需要注册什么公司,做推送实用网站,重庆sem优化最大公约数#xff1a;
概念#xff1a;
公约数中最大的称为最大公约数。 对任意的若干个正整数#xff0c;1总是它们的公因数。 公约数与公倍数相反#xff0c;就是既是A的约数同时也是B的约数的数#xff0c;12和15的公约数有1#xff0c;3#xff0c;最大公约数就是…最大公约数
概念
公约数中最大的称为最大公约数。 对任意的若干个正整数1总是它们的公因数。 公约数与公倍数相反就是既是A的约数同时也是B的约数的数12和15的公约数有13最大公约数就是3。
代码思路
采取辗转相除法——如果 a 和 b 是两个正整数且 ab 则a和b的最⼤公约数等于 b 和 a%b a 除以 b 所得的余数的最⼤公约数。
通过辗转相除法的原理我们可以明白在此处可能需要使用while的循环进行运算。
而循环的条件则是进入循环的二者能够进行完全的整除那么便得到了最大公约数。
代码展示
#include stdio.h
int main()
{int m 0;int n 0;scanf(%d %d, m, n);//18 24//辗转相除法int k 0;//当n不能整除m即k≠0更新两个最值重复步骤计算n与m%n的最⼤公约数while (k m % n){m n;n k;}printf(%d\n, n);return 0;
}最小公倍数
概念
指在两个或两个以上的自然数中如果它们有相同的倍数这些倍数就是它们的公倍数其中除0以外最小的一个公倍数叫做这几个数的最小公倍数。
代码思路
可以利用最小公倍数和最大公约数之间的关系——最⼩公倍数可以由两数乘积除以两数的最⼤公约数求得。
因此我们可以先使用辗转相除法求出最大公约数在将两个数相乘得到的积在除取最大公约数因此得到最小公倍数。
代码演示
#include stdio.h
int main()
{int m 0;int n 0;//输⼊scanf(%d %d, m, n);//18 24int k 0;int mul m*n;//辗转相除法求得最⼤公约数while (k m % n){m n;n k;}printf(%d\n, mul/n);return 0;
}
