GCD与LCM

求最大公约数(GCD)和求最小公倍数(LCM);

首先是求最大公约数,我们可以利用辗转相除法来求

1 int gcd(int a,int b)
2 {
3     if(b==0)
4         return a;
5     return gcd(b,a%b);
6 }

这就是GCD的核心代码。

剩下的LCM与gcd也有很大的关系,首先最大公约数也是最小公倍数的约数。

所以最小公倍数除掉最大公约数就剩下这两个数不相交的因子。

就比如12和8,提一个最大公约数4出来就只剩下3和2了。

而3*2则是他们不相交的因子。

所以最小公倍数就等于这两个数的乘积除以gcd;

 1 int gcd(int a,int b)
 2 {
 3      if(b==0)
 4          return a;
 5      return gcd(b,a%b);
 6 }
 7 int LCM(int a,int b)
 8 {
 9     return a*b/gcd(a,b);
10 }

 

上一篇:zabbix钉钉报警


下一篇:Ubuntu中遇到Unable to lock the administration directory (/var/lib/dpkg/),are you root?