本文主要介紹的是C語言常規的一道題，希望對于廣大讀者學習C語言有一些幫助。使用C語言求解a和b的最大公約數。該問題可以采用輾轉相除法去解決!

歐幾裡德算法又稱輾轉相除法,歐幾裡德算法是用來求兩個正整數最大公約數的算法。古希臘數學家歐幾裡德在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾裡德算法。擴展歐幾裡德算法可用于RSA加密等領域。

假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾裡德算法，是這樣進行的：

1997 / 615 = 3 (餘 152) 615 / 152 = 4(餘7) 152 / 7 = 21(餘5) 7 / 5 = 1 (餘2) 5 / 2 = 2 (餘1) 2 /1= 2 (餘0)

至此，最大公約數為1

以除數和餘數反複做除法運算，當餘數為 0 時，取當前算式除數為最大公約數，所以就得出了 1997 和 615 的最大公約數 1。

這種寫法是非常簡單的思路

1. 1.先求兩者中的最大值
2. 2.再用循環描述輾轉相除即可

源碼:

#include <stdio.h> #include <stdlib.h> int result(int m, int n) { int r; if (m>n) { r = m, m = n, n = r; } r = n%m; while (r != 0) { n = m; m = r; r = n%m; } return m; } int main() { printf("result:%d\n",result(12,9)); system("pause"); return 0; }

看到這個代碼，你的反應是不是黑人問号？？輾轉相除法，還能這麼寫？你寫了幾十行的代碼，别人隻用了簡單幾行的遞歸就實現的功能。有興趣的可以去嘗試下哦，源碼如下:

#include <stdio.h> #include <stdlib.h> int result(int m, int n) { return n ? result(n, m%n) : m; } int main() { printf("result:%d\n",result(12,9)); system("pause"); return 0; }

文章都是手打原創，每天最淺顯的介紹C語言、C ，windows知識，喜歡我的文章就關注一波吧，每天帶你學習C/C 不同的知識，也可以看到最新更新和之前發表的文章哦。如果足下基礎比較差，不妨關注下人人都可以學習的視頻教程

《C語言51課視頻教程合集》

《C 45課視頻教程》

通俗易懂，深入淺出，一個視頻隻講一個知識點。視頻不深奧，不需要鑽研，在公交、在地鐵、在廁所都可以觀看，随時随地漲姿勢

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!