最大公約數的基本原理:

兩個數的最大公約數是指能同時整除它們的最大正整數。
設兩數為a、b(a≥b)，求a和b最大公約數。

輾轉相除法

代碼如下：

//只截取了一部分，完整代碼可看下方 while (b<0){t = a % b;a = b;b = t;}

我們可以發現輾轉相除法，無非就是提供一個暫存變量t（或者是別的，這里只是方便舉例），使其儲存變量a%變量b的值（隱含條件a>b），然后使得較大變量（變量a）轉換為那個較小變量（變量b），而較小變量轉換為兩者的取余的值。并且當b=0跳出循環得到相應的最大公約數變量a。

這是一個非常經典的關于最大公約數的一個求法，該段代碼也取自如何得到最簡分式的例題。

完整的代碼如下：

#include <stdio.h>int main(){int dividend,divisor;scanf("%d/%d",&dividend,&divisor);int a = dividend;int b = divisor;int t;while (b<0){t = a % b;a = b;b = t;}printf("%d/%d\n",dividend/a,divisor/a);return 0; }

總結

以上是生活随笔為你收集整理的求最大公约数——辗转相除法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。