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;
  }

4.其他方法

int gcd(int a,int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;b=c;
    }
    return a;
}

关于最大公约数的一些结论：（不对）

求Sa（a1*a2*a3*a4*a5...）和Sb（b1*b2*b3*b4*b5...）的最大公约数

等于他们对应每一项的最大公约数的乘积。比如：

Sa=(4*3*1*5)=60

Sb=(2*6*2*3)=72

60和72的最大公约数是12。如果把他们单独拆开后，上下每一项对于的最大公约数分别是

2*3*2*1=12。结论一致。在计算中可以用这个公式，来缩小计算数的大小。