最大公约数和最小公倍数



最大公约数:辗转相除法

C代码
  1. /*  
  2.  * GCD(Greatest Common Divisor) 
  3.  * 辗转相除法求最大公约数 
  4.  */  
  5. public int GetGCD(int a, int b)  
  6. {  
  7.     int tmp;  
  8.     while (b != 0)  
  9.     {  
  10.         tmp = a % b;  
  11.         a = b;  
  12.         b = tmp;  
  13.     }  
  14.     return a;  
  15. }  

最小公倍数:

ab的最大公约数为GCD

ab的最小公倍数为LCM = a*b/GCD