转：最大公约数和最小公倍数的算法

转：http://www.cnblogs.com/binglingshui/archive/2009/01/04/1368592.html
http://topic.csdn.net/t/20060722/14/4897709.html

（1）最大公约数的求法：辗转相除法/Euclid(欧几里得）

先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。

假设求3与11，首先用11%3=2 ，再用3%2=12%1=0 ，即最后的1是最大公约数

int gcd(int a,int b)
      {  if (a < b) swap (a, b) ;
          if(b==0) return a;
          else return gcd(b,a%b);
      }

（2）两个数最小公倍数的求法
      两个数的积除于最大公约数即为最小公倍数。