用C语言对高中教材中关于计算最大公因数算法的实际检验

张凡

摘 要：最大公因数，在数学领域运用十分广泛，也是计算机领域自发展以来的热门话题之一。本文就高中数学课本中所罗列的辗转相除法与更相减损法以C语言为工具，对这两种算法在实际计算机的应用中做出的检验做出评价与分析，并给出实验的测试数据。

关键词：C语言;最大公因数;算法思想

中图分类号：TP311.11 文献标识码：A 文章编号：1671-2064（2019）04-0037-02

0 引言

我们在高中学习中，曾学习过一个章节算法与程序框图，这一章中，我们详细地了解了有关怎样寻找最大公因数的应用算法以及有关的程序框图，算法包括辗转相除法和更相减损法。在现代计算机社会中，一个算法能否在实际中快速有效地达到目的是非常重要的一个参考指标，它决定着算法的优劣。因此，本文旨在以实际操作的方式，对这两种算法进行深入的剖析研究，并对其实用性做出论定。最大公因数，又称最大公约数，是指两个或两个以上整数共有约数中最大的一个，本文着重介绍对两个数最大公约数的实际检验。

1 质因数分解法

学生时代刚刚接触到最大公因数这个概念的时候，老师通常会让我们使用质因数分解法。所谓质因数分解，它指的是将一个合数（除了1和自身外还有其他因数的数）分解为若干质数（只有1和自身这两个因数）的乘积的形式。举个简单的例子，对于数字180，我们对从2开始的质数进行逐个的检验，首先：180=2*90，那么可以分解出了一个2;继续分解，90=2*45，这个时候，不难发现45不能被2整除，那么可以检验是否能被3整除，通过45=3*15，15=3*5这两个算式，可以得到了5，而5是一个质数，故分解完毕后180=2*2*3*3*5。那么如果要计算180和120的最大公因数，只需要对120也做上述工作，这样可以得到120=2*2*2*3 *5，再将两个数字分解后多个质因数中的相同部分，选出并计算其乘积，如对180和120进行上述运算可以得到2*2*3*5=60，那么180和120的最大公因数就是60。

质因数分解法，看似非常简单的一个方法，在计算机程序的运行中却很少涉及，其原因在于计算机的运行方式和人不同，计算机更习惯于重复的、循环的、相同的任务体系。对于计算机，我们要寻求更加方便“计算机”领悟的方法技巧，这也是本文接下来要给大家介绍的这两种方法。

2 辗转相除法

2.1 算法原理

辗转相除法[2]，最早是由欧几里得在公元前300年左右提出的，因此又叫欧几里得算法。它是指用开始的两个数（本文只讨论两数中最大公约数的求法，下同）中较大的数除以较小的数，得到商和余数，由于初始两数与所得余数的最大公因数相等，所以用较小的数和余数重复上述过程，最终得到两个数，其中一个能被另一个整除。在计算机的算法中，这种重复的、可操作性强的方法，比起传统的质因数分解法，它更适合计算机程序进行工作。

我们先来看一下这种算法的普通应用。以高中教材的数据为例，使用辗转相除法求8251和6105的最大公因数，首先用其中较大的那个数除以较小数，所得商和余数8251=6105*1+2146。通过这个式子，可以得到了余数2146。由最大公因数的定义可知，6105、8251以及所得余数2146它们的最大公约数其实是相等的，那么接下来只需要计算6105与2146的最大公约数，这无疑大大地减少了计算量，距离得到结果又更近了一步。

我们对6105和2146重复上述步骤（使用辗转相除的时候，我们尽量选择较小的两个数，这样可以大大地减少计算量）：

6105=2146*2+1813

2146=1813*1+333

1813=333*5+148

333=148*2+37

148=37*4

到这里，不难发现，我们得到了一个无法取余的式子，那么这个时候，求出的最大公约数即为37。

2.2 算法实现

经过对辗转相除的尝试，可以初步了解辗转相除法的基本流程，对于其在计算机上的实用性，我们采用了最常用的开发工具Microsoft Visual C++进行了实验的检测[1，4]，整个程序与算法所使用的方式基本一致，我们首先采用了课本中所给出的数据，并且类似地进行了以下几组实验：

实验所用代码如下：

#include

int main（）

{

int a，b，m;

printf（"请输入两个正整数，该程序将使用辗转相除法求其最大公因数：a="）;

scanf（"%d"，&a）;

printf（"b="）;

scanf（"%d"，&b）;

while（a%b！=0）

{

m=a%b;

a=b;b=m;

}

printf（"a与b最大公因数为%d＼n"，b）;

return 0;

}

2.3 算法结果及评价

将实验中所使用的数据列成一张表格，实验结果如表1所示。

对于每一个实验，均采用了变量交换的方法进行验证，这样做可以更全面地确定实验的准确性与完整性。除去课本上的例子，我们还选取了一组数值较大且明显互质的数字进行检验。

计算机所呈现出来的结果与我们所预想的结果基本一致，在重重考核下，计算机都出色地完成了任务。此后进行的其他多组重复数据，也向我们证实了辗转相除法在计算機领域中应用的优势。

那么是不是直接使用辗转相除计算最大公因数就可以了呢？当然不是，从数据结构的角度而言，辗转相除还有许多不够完善的方面。诸如，当我们涉及到较大的变量时，由于计算机的除法运算和我们的除法运算的机理是完全不同的，计算机的除法需要进行许多额外的繁杂工作，这样高额的除法运算量所带来的工作量在实际生产生活中无疑会带来巨大的成本问题。

3 更相减损法

3.1 算法原理

更相减损术出自《九章算术》，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之”。用现在的话来讲，就是先判断是否都为偶数，用2约减后，再以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数大小相等为止，则这个数与开始约减的数乘积即为所求最大公约数[3]。

也就是说，辗转相除法分为两个步骤，一个步骤为“约减”，另一个为“减损”，举个例子，我们计算196和126的最大公因数，首先这两个数都是偶数，那么同时将其除以2，得到98和63。显然，98和63的最大公因数也是196和126的公因数，只是比196和126的最大公因数要少了一半。进行这个环节以后，由于63不是偶数，那么约减完毕，接下来就是进行减损工作。把98和63以大数减小数，并进行“辗转相减”，得到：

98-63=35;63-35=28;35-28=7;28-7=14;14-7=7

由于进行最后一步操作后得到的是两个相等的整数，那么7就是98和63的最大公因数了（这也侧面反映了计算两个奇数的最大公因数，使用辗转相减法是个非常不错的方法）。但是要计算196和126的最大公因数，我们还要将7乘上刚才所约掉的2。

3.2 算法实现

如同辗转相除法，针对更相减损法，我们也进行了实际检验的过程，所使用的代码如下：

#include

int main（）

{

long a，b，m，t，r;

printf（"请输入两个正整数，该程序将使用更相减损法求其最大公因数：a="）;

scanf（"%d"，&a）;

printf（"b="）;

scanf（"%d"，&b）;

t=1;

while（（a%2==0）&&（b%2==0））

{

t=t*2;

a=a/2;

b=b/2;

}

while（1）

{

if（a

{

r=b;

b=a;

a=r;

}

while（（a！=b）&&（a>b））

{

m=b;

b=a-b;

a=m;

}

if（a==b） break;

}

a=a*t;

printf（"a与b最大公因数为%d＼n"，a）;

return 0;

}

3.3 算法结果及评价

更相减损实验结果，如表2所示。

经过实验可以发现，更相减损法也是计算最大公因数的良好途径之一。然而实验发现，更相减损所需要的代码比辗转相除多一倍之多，此时我们要将约减和减损分开作为一个程序的两个不同的部分进行分别处理。而如果去掉约减环节，大量的迭代会使较大的、有一定规律的数据的处理效率显著降低。比如计算999999和3的最大公因数，使用辗转相除法可以一步到位，然而使用更相减损却要进行巨大的工作量。除了约减的繁琐以外，每循环一次，都要进行一次对变量a，b的大小比较，也就是说，这一程序一共需要进行三次不同的循环迭代，包括一个循环的嵌套，在一个较大的程序中，计算最大公因数不过是一个极小的环節而已，如果这样一个小环节都需要耗费如此经历，那么这个算法也是不够成熟的。

4 结语

虽然说计算两个数的最大公因数，在我们看来也许是非常简单容易的操作，但是在现代的计算机领域却仍然存在各种各样的问题。除了高中数学课本中给我们所展示的这两种算法外，计算两个数的最大公因数的办法还有许多，许多方法仍然需要我们去不断完善与修改。相信在科技的不断发展中，一定会有更加完美的算法去适应当今的时代趋势。

参考文献

[1] 谭浩强.C程序设计（第四版）[J].计算机教育，2010，No.128（20）：113-113.

[2] 边晶，杜威.深入探析计算机求解大整数最大公约数问题[J].长春大学学报，2012，（12）：1476-1479.

[3] 邱建林，刘维富，顾晖.C语言程序设计教学的研究与实践[J].电气电子教学学报，2003，25（4）：96-98.

[4] 黄定华，孙炳达.嵌入式系统中的软件设计技术──语言程序设计[J].工业控制计算机，2001，14（5）：3-6.