一、辗转相除法

也叫欧几里德算法

例如c语言求最大公约数，求gcd（319，377）：

∵ 377÷319=1（余58）

∴gcd（319，377）=gcd（319，58）；

∵ 319÷58=5（余29），

∴ gcd（319，58）=gcd（58，29）；

∵ 58÷29=2（余0），

∴ gcd（58，29）= 29；

∴ gcd（319，377）=29.

#include
int main(){
    int u=319,v=377,temp=0;
     while(v!=0){
        temp=u%v;
        u=v;
        v=temp;
     }
     printf("The largest common divisor:%d",u);
    return 0;
}

二、更相减损法

出自《九章算术》“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

例1．用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

这个过程可以简单的写为：

（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.

例2．用更相减损术求260和104的最大公约数。

解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。

此时65是奇数而26不是奇数c语言求最大公约数，故把65和26辗转相减：

65-26=39

39-26=13

26-13=13

所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。

这个过程可以简单地写为：

（260,104）(/2/2) =>（65,26）=（39,26）=（13,26）=（13,13）=13. (*2*2) => 52

#include
#include
int main(){
    int a=0,b=0,count=0,multi=0;
    scanf("%d%d",&a,&b);
     while(a%2==0 && b%2==0){
        a/=2; b/=2;
        count++;
     }
     while(a!=b){
        if(a>b) a=a-b;
        else b=b-a;
     }
     multi=pow(2,count);
     printf("The largest common divisor:%d",a*multi);
    return 0;
}

三、穷举法

简单来说，就是选两个数a、b中的较小值min，然后因数 i 从min开始递减穷举，当满足这两个数模以 i 等于0时，此时 i 就为最大公因数。

#include
int main (){
   int a=0,b=0,i=0,min=0;
   scanf ("%d%d",&a,&b);
   min=a//两者最小
   for (i=min; ; i--) //穷举
       if ( a%i == 0 && b%i ==0 )
           break;
   printf("The largest common divisor:%d\n", i);
} 

引用：

百度百科