最大公約數的演算法

『壹』 3個數最大公約數演算法

求3個數的最大公約數的演算法主要有兩種：輾轉相除法和更相減損術。

1. 輾轉相除法： 在3個數中任意選擇2個數。 對於選定的兩個數，用較大的數除以較小的數。 如果余數不為零，則用余數和較小的數構成新的一對數，繼續執行除法操作。 重復上述步驟，直到余數為零，此時較小的數即為這兩個數的最大公約數。 將得到的最大公約數與第三個數再次應用輾轉相除法，求得最終結果即為三個數的最大公約數。

2. 更相減損術： 同樣在3個數中任意選擇2個數。 對於選定的兩個數，用較大的數減去較小的數，得到差值。 將差值和較小的數構成新的一對數。 重復執行減法操作，直到差值和較小的數相等。 此時相等的兩數即為這兩個數的最大公約數。 將得到的最大公約數與第三個數再次應用更相減損術，求得最終結果即為三個數的最大公約數。