最小公倍数:
数论中的一种概念,两个整数公有的倍数成为他们的公倍数
其中一个最小的公倍数是他们的最小公倍数
同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数
求最小公倍数算法:
最小公倍数=两整数的乘积÷最大公约数
求最大公约数算法:
(1) 辗转相除法
有两整数a和b:
- a%b得余数c
- 若c=0,则b即为两数的最大公约数
- 若c≠0,则a=b,b=c,再回去执行1
例如:求27和15的最大公约数过程为
- 27÷15余12
- 5÷12余3
- 12÷3余0
因此,3即为最大公约数
代码实现:
1 | /** |