求两个数的最大公约数（编程之美上有解答）

这里所使用的其实就是阿基里德算法，求两个数的最大公约数。

算法过程： 比如求 17与6的最大公约数

令M=17，N=6；

第一次：R=M%N=5;  M=N=6； N =R=5

第二次:  R=M%N = 1; M=N=5;  N=R=1;

第三次: R=M%N =0， M=N=1，N=R=0。

所以结束条件为if(N==0)

返回                     return M

 

/* 求两个数的最大公约数 */

#include<stdio.h> #include<time.h> #include<stdlib.h>

void init_num(long int *x,long int *y) {  int i;  srand( (unsigned)time( NULL ) );  for(i=0;i<65536;i++)  {   srand( (unsigned)time( NULL ) );   x[i]=rand();   srand( (unsigned)time( NULL ) );   y[i]=rand();  } } long int gcd_one(long int x,long int y) {  if(y==0)   return x;  else   return gcd_one(y,x%y); }

long int gcd_two(long int x,long int y) {  if(y==0)   return x;  else if(x<y)   return gcd_two(y,x);

 else   return gcd_two(y,x-y);

}

int  IsEven(long int x)  /*是偶数的话返回1*/ {  if(x&1)   return 0;  else   return 1; } long int gcd_three(long int x, long int y) {  if(y==0)   return x;  else if(x<y)   return gcd_three(y,x);  else  {   if(IsEven(x))   {    if(IsEven(y))    {     return (gcd_three(x>>1, y>>1) )<<1;    }    else    {     return (gcd_three(x>>1,y) );    }   }

  else   {    if(IsEven(y) )    {     return (gcd_three(x,y>>1) );    }    else    {     return (gcd_three(y,x-y) );    }   }  } }

 

int main() {  clock_t start,finish;  double difTime;  int x[65536];  int y[65536];  int i;  init_num(x,y);

 start=clock();  for(i=0;i<65536;i++)  {   gcd_two(x[i],y[i]);  }

 printf("gcd  is %ld/n",gcd_one(x[100],y[100]));  printf("gcd  is %ld/n",gcd_two(x[100],y[100]));  printf("gcd  is %ld/n",gcd_three(x[100],y[100]));

 finish=clock();  difTime=(double)(finish-start)/CLOCKS_PER_SEC;  printf("use %f secons/n",difTime);

   return 0; }