静态网站怎么做优化,微信公众号人工服务电话,免费在线网页代理,重庆注册公司流程和费用标准题目#xff1a;输入两个正整数a和b#xff0c;求其最大公约数和最小公倍数
数学#xff1a;最大公约数*最小公倍数a*b
例如#xff1a;a16#xff0c;b20。最小公倍数80#xff0c;最大公约数4。80*416*20。
算法#xff1a;辗转相除法#xff0c;又称欧几里德算法…题目输入两个正整数a和b求其最大公约数和最小公倍数
数学最大公约数*最小公倍数a*b
例如a16b20。最小公倍数80最大公约数4。80*416*20。
算法辗转相除法又称欧几里德算法。
将大的那个数作为a小的为b。
a % b r a b将 b 的值赋给 a b r将 r 的值赋给 b 作为下一次的计算
a % b r
······
直到
a % b r 0
最后这一步得到的 b 就是 最大公约数。
例如
20 / 16 1 ······ 4
16 / 4 4 ······ 0
于是大公约数b 4
再例 程序实现
#include stdio.hint main()
{int a16,b20,r;//经实验发现并不需要把大的数放在前面do{ra%b;ab;br;} while(r);printf(最大公约数是%d\n,a);return 0;
}
输出
最大公约数是4 实验发现并不用把大的数作为被除数。因为
16 % 20 0 ······ 16
20 % 16 1 ······ 4
在做下一步取模运算时就将这两个数置换过来了 完整程序实现
#include stdio.hint main()
{int a,b,r;printf(请输入两个整数);scanf(%d %d,a,b);int ca*b;//存数据do{ra%b;ab;br;} while(r);printf(最大公约数是%d\n,a);printf(最小公倍数是%d\n,c/a);return 0;
}
Sample Output 1:
请输入两个整数16 20
最大公约数是4
最小公倍数是80
Sample Output 2:
请输入两个整数75 125
最大公约数是25
最小公倍数是375
