一、实验名称：求2个数的最大公约数 二、实验内容：利用辗转相除法、更相损减法、穷举法、Stein算法求两个数的最大公因数。并且比较这四种算法的运行时间。 三、算法设计和代码部分 1、辗转相除法 辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： a b=0

gcd(a,b) =

gcd(b,a mod b) b!=0 其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，c为余数 1、大数放a中、小数放b中； 2、求a/b的余数； 3、若c=0则b为最大公约数； 4、如果c!=0则把b的值给a、c的值给a； 5、返回第二步； 代码： #include int main() { int a=0; int b=0; int c=0; printf(“辗转相除法\n”); printf(“请输入第一个数：\n”); scanf("%d",&a); printf(“请输入第二个数：\n”); scanf("%d",&b);

} 辗转相除法算法流程图：

2、更相损减法 更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

代码： #include #include int main() { int a=0; int b=0; int c=0; int i=0; printf(“求两个数的最大公约数\n”); printf(“请输入第一个数的值：\n”); scanf("%d",&a); printf(“请输入第二个数的值：\n”); scanf("%d",&b);

} 更相损减法算法流程图：

3、穷举法 穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。 代码： #include

int way(int a,int b) { int c; if(a0) { if(a%c0&&b%c0) break; else c–; } return ©; }

int main() { int m,n,v; printf(“请输入两个数的值：\n”); scanf("%d%d",&m,&n); v=way(m,n); printf("\n这两个数的最大公因数是：\n%d\n",v); return 0; } 穷举法算法流程图：

4、Stein算法 Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况如何化小呢？ 先来看看一奇一偶的情况： 设有2x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以 a = gcd( 2x,y ) 是奇数。根据2x是个偶数不难联想到，a应该是x的约数。我们来证明一下：(2x)%a=0，设2x=na，因为a是奇数，2x是偶数，则必有n是偶数。又因为 x=(n/2)*a，所以 x%a=0，即a是x的约数。因为a也是y的约数，所以a是x和y的公约数，有 gcd( 2x,y ) 1, v); else // both u and v are even return gcd(u >> 1, v >> 1) > 1); // reduce larger argument if (u > v) return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u); }

int main() { int a=0; int b=0; int c=0; printf(“求两个数的最大公约数\n”); printf(“请输入第一个数的值：\n”); scanf("%d",&a); printf(“请输入第二个数的值：\n”); scanf("%d",&b); c=gcd(a,b); printf("\n最大公约数为%d\n",c); return 0; } 算法流程图：

无

，一共是4个算法。我先接触时，是先思考各种方法如何解决这个问题的。通过上机说明和百度搜索，我先后理解辗转相除法和更相损减法，并且将这两个算法的流程图画好。并且在用代码实现自己的流程图时，感觉十分的流畅。 但是我在穷举法这却出现了问题。穷举法的思维很简单，所以我没有先画流程图，但是在用代码实现这个问题的时候，我发现我的代码总会出现一个问题： Linking… LIBCD.lib(crt0.obj) : error LNK2001: unresolved external symbol _main Debug/123.exe : fatal error LNK1120: 1 unresolved externals 执行 link.exe 时出错.

123.exe - 1 error(s), 0 warning(s) 目前问题还没解决，代码参考了上机说明，我会进一步把问题搞清楚。关于stein算法，刚开始理解是用于优化，最后还得靠前三种方法解决，但是代码无法理解，还得继续思考这个问题。