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。结论一致。在计算中可以用这个公式，来缩小计算数的大小。

(adsbygoogle = window.adsbygoogle || []).push({});