求最大公约数和最小公倍数
假设有两个数a和b,求a,b的最大公约数和最小公倍数实际上是一个问题,得出这两个数的最大公约数就可以算出它们的最小公倍数。
最小公倍数的公式是 a*b/m
m为最大公约数
因为 a=m*i; b=m*j;
最小公倍数为 m*i*j
计算a和b的最大公约数的方法:
方法一:
更相损减法:
反复把两数的最大者减去最小者,直至两数相等,这个数就是最大公约数
如 4 和 6
6-4=2
2个数变成了4和2
4-2=2
两个数变成了2和2
2=2 即2是两数的最大公约数
方法二:
辗转相除法:
大致原理类似于 更相损减法
a>b
a%b的余数为r