最大公约数与最小公倍数算法整理

最大公约数：能够同时被两个数整除的那个最大的数。

最小公倍数：两个整数公有的倍数成为他们的公倍数，其中一个最小的公倍数是他们的最小公倍数。

最小公倍数=两整数的乘积÷最大公约数反之同理。

最大公约数算法：

1.GCD算法(欧几里得算法):

定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

 1 int gcd(int a,int b)  
 2 {  
 3     int r;  
 4     while(b>0)  
 5     {  
 6          r=a%b;  
 7          a=b;  
 8          b=r;  
 9     }  
10     return a;  
11 }

以上是GCD算法的基础模运算实现，即辗转相除法。

位运算计算：

1 int gcd(int a,int b)  
2 {  
3     while(b^=a^=b^=a%=b);  
4     return a;  
5 }

递归方式实现：

1 int gcd(int a,int b)  
2 {  
3     return (b>0)?gcd(b,a%b):a;  
4 }

2.相减法：

有两整数a和b：

① 若a>b，则a=a-b

② 若a<b，则b=b-a

③ 若a=b，则a（或b）即为两数的最大公约数

④ 若a≠b，则再回去执行①

例如求27和15的最大公约数过程为：

27－15＝12( 15>12 ) 15－12＝3( 12>3 )

12－3＝9( 9>3 ) 9－3＝6( 6>3 )

6－3＝3( 3==3 )

因此，3即为最大公约数

1   /* a, b不相等，大数减小数，直到相等为止。*/   
2    while ( a!=b)   
3          if (a>b)  a=a-b;       
4          else  b=b-a;

3.穷举法

穷举法，即暴力算法，

有两整数a和b：

① i=1

② 若a，b能同时被i整除，则t＝i

③ i++

④ 若 i <= a(或b)，则再回去执行②

⑤ 若 i > a(或b)，则t即为最大公约数，结束

改进：

① i= a(或b)

② 若a，b能同时被i整除，则i即为最大公约数，

结束

③ i--，再回去执行②

有两整数a和b：

① i=1

② 若a，b能同时被i整除，则t＝i

③ i++

④ 若 i <= a(或b)，则再回去执行②

⑤ 若 i > a(或b)，则t即为最大公约数，结束

改进：

① i= a(或b)

② 若a，b能同时被i整除，则i即为最大公约数，

结束

③ i--，再回去执行②

1 /*穷举法求最大公约数*/ 
2 for (t= a; t>0; t-- )     
3     if ( a%t == 0 && b%t ==0 )    
4     break;

1     /*穷举法求最小公倍数*/ 
2      for (i= a; ; i++ )  
3          if ( i % a == 0 && i % b ==0 ) 
4          break;