算法之【輾轉相除法】

輾轉相除法用于求兩個或以上的正整數的最大公約數。

The Euclidean Algorithm

is used to get the greatest common divisor.

語言描述：求兩個整數的最大公約數時，先讓一個整數整除另一個整數，求得餘數，再分别将剛才的除數和餘數作為新的被除數和除數進行運算，依次循環直到餘數為0時停止，此時的除數就是剛開始兩個數的最大公因子。用已求出的公因數和第三個整數再經過一次輾轉相除法就求得三個數的最大公因數，以此類推。

Description：To find the

greatest common divisor of two integers, firstly let one

integerdivided by the other integer, the remainder is obtained,

then regard the divisorand remainder as a new dividend and divisor

respectively, and calculate again, until the final remainder is

zero. Now the divisor is just the wanted greatest common divisor.

Then compute the number along with a third integer through

Euclidean Algorithm to get the greatest common divisor of three,

and so on. 

C語言函數表達式：

C language description：

int fun(int a,int b) 

{

   int

t;

while(b)

           t

= a%b;

           a

= b;

           b

= t;

}

               return

a;