c语言求最大公约数和最小公倍数

求最大公约数和最小公倍数

假设有两个数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 

上一篇:docker 配置远程访问证书验证


下一篇:instanceof