欧几里得算法

什么是GCD？ 
GCD是最大公约数的简称（当然理解为我们伟大的党也未尝不可）。在开头，我们先下几个定义： 
①a|b表示a能整除b（a是b的约数） 
②a mod b表示a-[a/b]b（[a/b]在Pascal中相当于a div b）
③gcd(a,b)表示a和b的最大公约数 
④a和b的线性组合表示ax+by（x,y为整数）。我们有：若d|a且d|b，则d|ax+by（这很重要！）

欧几里得算法又称为辗转相除法，设两个数 a,b则 a,b的最大公约 gcd(a,b)=gcd(b,a%b) 不妨设 a>=b,c=gcd(a,b),a=kc,b=jc,则 k,j 互素（否则 c 不是 a,b 的最大公约数） ，则设r=a%b 则 a=mb+r, 则 r=a-mb=kc-mjc=(k-mj)c, 因为 k,j 互素，则 k-mj 与 j 互素gcd(a,b)=gcd(b,a%b)

//非递归版，C语言实现 
int gcd(int a,int b) 
{ 
    if(!a) 
      return b; 
    int c; 
    while(b) 
    { 
        c=b; 
        b=a%b; 
        a=c; 
    } 
    return a; 
} 

//递归版，C语言实现 
int gcd(int a,int b) 
{ 
 if(b==0) 
   return a; 
 return gcd(b,a%b); 
} 

 一般很少有题目只要求最大公约数，但是通常很多题会用到求最大公约数的过程，比如判断两个数是否互素（最大公约数为 1） ，这个时候欧几里得算法暨辗转相除法就变成了很得力的工具，因为每一步都是取模，保证了数据减小的速度特别快。能够在很短的时间内求出两个数的最大公约数。