用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.