一、实验内容
运行最大公约数通用算法，对程序进行调谐和测试。 需要添加编程风格良好、输入不正确等异常处理模块。
二.算法
1 .辗转相除
在换相除法(别名欧几里得法) c语言中，用于计算两个正整数a、b的最大公约数和最小公倍数，实质上依赖于以下定理：
该定理允许使用函数嵌套调用和递归调用的形式来确定两个最大公约数和最小公倍数，如下所述
//非递归实现：公共int divisor (inta，int b )/*自定义函数是两个数的最大公约数() */{ int temp； /*定义整数变量*/if(ab )/*，通过比较得出两个数中的最大值和最小值() */{ temp=a； a=b； b=temp； (/)设定中间变量进行两数交换(/while ) ) b！=0(() ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) a=b ) ) ) ) ) ) ) ) ) ) ) )这是本产品的性能/*变量的数值交换*/b=temp； (返回) a； /*返回最大公约数给调用函数的*/}//递归实现：公共输入gcd (inta，int b ) if ) a%b==0)返回b； else返回gcd (b，a%b )； )辗转相除法程序流程图：
2 .穷举法(利用数学定义) ) ) )。
穷举法(也称为枚举法)穷举法是求两个正整数的最大公约数的解题步骤。 从两个数中从小到大依次列举，得到的公约数为最大公约数，直到找到公约数并立即中断列举。
//非递归实现：公共int divisor (inta，int b )/*自定义函数是两个数的最大公约数() */{ int temp； /*是否定义整数变量*/temp=(ab )？ b:a； /*采种条件运算式如果找到两个数中最小值*/while(temp0) if(a%temp==0b%temp==0) )能同时被a、b整除的数，则中止循环) */break； 特普- -；/*如果不满足if条件，变量可以被a和b整除*/}返回(时间)； 将满足/*条件的计数返回主调函数的*/} c程序流程图：
*3.更相损法
此外，减损术是一种求解《九章算术》出的最大公约数的算法，原本是为约分而设计的，但适用于需要最大公约数的情况。 《九章算术》是中国古代的数学专著，其中“更相减损术”可用于求两个个数的最大公约数，即“可半之、不可半之、次置母数、少减多、更相减损、求其等”。 用等数约定。 ”
翻译成现代语言如下。
步骤1 :任意给出两个正整数； 判断它们是否都是偶数。 如果是2，约简； 否则，执行步骤2。
第二步：用大的数减少小的数，接下来把得到的差和小的数进行比较，用大的数减少数。 继续此操作，直到获得的减数和差值相等。
这是在第一步中约束掉的几个2和第二步中数量的乘积所要求的最大公约数。
其中“等数”是最大公约数。 求“等数”的方法是“更耗”法。 所以，更相减损法也称为等值算法。
//非递归实现：公共int divisor (intm，int n ) {int i=0，temp，x； 判断while(m%2==0n%2==0)/m和n能被几个2整除({m/=2； n/=2； i=1； //i保存同时可去除的2个个数(if ) Mn )/m保存较大的值) {temp=m； m=n； n=temp； }while(true ) ) {x=m-n； //m减去n的m=(NX )？ n:x； //将减法后的差和被减数大的放入Mn=(NX )中吗？ n:x； //减法后差和被减数小的为NIF(0==(m-n ) ) )break，直到被减数差相等； (if ) I==0)返回n； ELSEreturn(int ) Math.pow(2) 2，I ) *n； }程序流程图：
4.Stein算法
Stein算法是Stein在1961年提出的，该方法也是计算两个数的最大公约数。
对于两个正整数xy :
1 .均为偶数gcd(x，y )=2g CD (x/2，y/2 )；
2 .均为奇数gcd(x，y )=gcd ) ) xy )/2，) x-y )/2 )；
2.x奇y偶gcd(x，y ) gcd(x，y/2 )；
3.x偶y奇gcd(x，y )=gcd(y(y ) x/2，y )或gcd(x，y )=gcd(y(y，x/2 )；
5.gcd(x，x )=x，退出条件。
//非递归实现：公共int divisor (intx，I
nt y ){ int factor = 0; int temp; if ( x < y ) //比较大小 x存储大的 y存储小的 { temp = x; x = y; y = temp; } if ( 0 == y ) { return 0; } while ( x != y ) { if ( x%2!=0 ) {/*当x为奇数时 */ if ( y%2!=0 ) {/* 当x和y都是奇数时 */ y = ( x - y ) >> 1; x -= y; } else {/* 当x为奇数 y为偶数时 */ y >>= 1; } } else {/* 当x为偶数时 */ if ( y%2!=0 ) {/* 当x为偶数 y为奇数时 */ x >>= 1; if ( x < y ) { temp = x; x = y; y = temp; } } else {/* 当x和y都为偶数时 */ x >>= 1; y >>= 1; ++factor; } } } return ( x << factor );}//递归实现：public int gcd(int u,int v){ if (u == 0) return v; if (v == 0) return u; if (u%2==0) // u是偶数 { if (v%2!=0) //u是偶数 v是奇数 return gcd(u >> 1, v); else // u和v都是偶数 return gcd(u >> 1, v >> 1) << 1; } if (v%2==0) // u是奇数 v是偶数 return gcd(u, v >> 1); // u和v都是奇数 if (u > v) return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u);}程序流程图：
四、总结
经过自己的动手实验，由最后的结果可知对于四种算法，枚举法的效率最低，其次是stein算法，再次是更相减损术；辗转相除法的效率最高。由于是随机产生的数字，这个结果只能代表一部分。下面我们来仔细分析一下各种算法：
对于辗转相除法相除数，在随机产生的整数中效率最高，其时间复杂度是对数量级O（log n）的，但对特别大的两个质数的效率就不太尽如人意。
对于更相减损术，其时间复杂度是O(n)，特别是在两个数相差很时候，效率最差，比如999与1,要进行998减法运算。
对于枚举法，其时间复杂度也是O(n)数量级的，但他只对两个数相差很大的时候并且其中一个数较小时，才效率高。
对同一算法的非递归实现与递归实现，由于现在的计算机内存都特别大，在数据量小的时候，并看不出效率上的差异。
对于stein算法，是针对辗转相除法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。其时间复杂度也是对数量级的，但由于stein算法是除法但嵌套导致其实际效率还不如更相减损术，只又在大质数的时候能由于辗转相除法。
在实验中遇到最多的bug，是对零的处理。零有没有约数？零与一个整数有没有公倍数？
由于我对数论了解甚少，网上有两种说法：
① 任意整数和0的公约数是该整数的所有约数
它们的最大公约数为该整数本身
因为0被所有非0整数整除,所以任意非零的整数都是0的约数
② 根据定义：如果一个整数能被另一个整数整除,那么第二个整数就是第一个整数的约数.约数是有限的,一般用最大公约数. 0既不是质数也不是合数 且他没有任何约数
为了方便处理，我采取了第二种说法，对输入进行判断，如果是输入零就直接返回零不做处理。在产生随机数的时候，也规避了产生零。
在stein算法中，用到了以为运算符>>来进行除二处理，我分别用/2与>>1进行了替换比较发现>>的效率比除法高了不少。