輾轉(zhuǎn)相除法的算法步驟

輾轉(zhuǎn)相除法的算法步驟為，兩個(gè)數(shù)中用較大數(shù)除以較小數(shù)，再用出現(xiàn)的余數(shù)（第一余數(shù)）去除除數(shù)，再用出現(xiàn)的余數(shù)（第二余數(shù)）去除第一余數(shù)，如此反復(fù)，直到最后余數(shù)是0為止。得到最后的除數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)。

輾轉(zhuǎn)相除法， 又名歐幾里德算法，是求最大公約數(shù)的一種方法。以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，最終當(dāng)余數(shù)為 0 時(shí)，取當(dāng)前算式除數(shù)為最大公約數(shù)。算法舉例：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 /1= 2 (余0)

至此，得出1997 和 615 的最大公約數(shù)為1。