1、欧几里得算法
1.1原理阐述
欧几里得算法求最大公约数原理主要依赖于以下定理：（a,b）=（b,a%b）。其证明过程如下：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则有d|a,d|b，而r=a-kb，因此d|r因此d也是（b,amodb）的公约数因此（a,b）和（b,amodb）的公约数是一样的，其最大公约数也必然相等，得证。1.2算法设计
欧几里得算法通过对两数进行求余，利用（a,b）=（b,a%b）定理不断反复循环，可以得到两者的最大公约数。具体流程图如下：开始对a和b进行赋值b=ta=bt=mod（a，b）a%b=0Y输出最大公约数bN结束11.3C语言编程实现
以下是C语言程序代码：#includelongEucli(longa,longb,long&n){if(b==0)returna;{n=n+1;returnEucli(b,a%b,n);}}intmain(){longa,b,n=0,d,t=0;printf(\"enterthefirstnumber:\\n\");scanf(\"%ld\printf(\"enterthesecondnumber:\\n\");scanf(\"%ld\if(a2.1原理阐述扩展欧几里德算法是用来在已知a,b求解一组x和y，使它们满足等式：ax+by=(a,b)=d（解一定存在，根据数论中的相关定理）。即对于不完全为0的非负整数a，b，（a,b）表示a，b的最大公约数，必然存在整数对x和y，使得（a，b）=ax+by。2.2算法设计
扩展欧几里得算法，精髓在于对x和y的赋值。对于a'=b,b'=a%b而言，我们求得x,y使得a'x+b'y=Gcd(a',b')由于b'=a%b=a-a/b*b那么可以得到:a'x+b'y=Gcd(a',b')，因而bx+(a-a/b*b)，y=Gcd(a',b')=Gcd(a,b)进而可得ay+b(x-a/b*y)=Gcd(a,b)因此对于a和b而言，他们的相对应的p，q分别是y和(x-a/b*y)。具体流程图如下：开始输入a和bx=ty=x-(a/b)*yt=yb=0输出最大公约数a*x+b*y结束32.3C语言编程实现
以下是C语言程序代码：#includelongexEucli(longa,longb,long&x,long&y,long&n){if(b==0){x=1;y=0;returna;}n+=1;longr=exEucli(b,a%b,x,y,n);longt=y;y=x-(a/b)*y;x=t;returnr;}intmain(){longa,b,x,y,n=0,t;printf(\"enterthefirstnumber:\\n\");scanf(\"%ld\printf(\"enterthesecondnumber:\\n\");scanf(\"%ld\if(a通过对两种算法的原理进行研究，再结合以上两张截图，我们发现，对12345678和76512348两数进行最大公约数的求解中，两种递归算法的迭代次数都是12次。但是，有所不同的是，在欧几里得算法中，每次迭代进行的操作是对a和b求余数。而在扩展欧几里得算法中，每次迭代时，除了要做一次求商的之外，还要做一次乘法和减法。因此，运用欧几里得算法和扩展欧几里得算法对两个整数求最大公约数时，欧几里得算法更为高效。5
