求最大公约数的方法

1.辗转相除法

int gcd(int a,int b)

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

2.穷举法

int divisor (int a, int b) //自定义函数求两数的最大公约数

 {
      int  temp;//定义整型变量
     temp=(a>b)?b:a;//采种条件运算表达式求出两个数中的最小值
     while(temp>0)

      {
              if(a%temp==0&&b%temp==0)//只要找到一个数能同时被a,b所整除，则中止循环
              break;
              temp--;//如不满足if条件则变量自减，直到能被a,b所整除 
      } 
     return (temp);//返回满足条件的数到主调函数处 
  } 

3.更相减损法

 int gcd2(int m,int n)
 {
     int i=0,temp,x;
     while(m%2==0&&n%2==0)//判断m和n能被多少个2整除
    {
         m/=2;
         n/=2;
         i+=1;
    } 
     if(m<n)//m保存大的值
   {
        temp=m;
        m=n;
        n=temp;
   } 
     while(x)
   {
        x=m-n;
        m=(n>x)?n:x;
        n=(n<x)?n:x;
        if(n==(m-n))
        break;
   }
    if(i==0)
    return n;
        else
        return (int) pow(2,i)*n;
  } 

返回目录：学习与质数/C++