如何求最大公約數

一、知識概述

1 輾轉相除法求兩個數的最大公約數

算法步驟描述為：

①輸入兩個正整數m和n(要求m>n)

②求余數r：計算m除以n，將所得余數存放到變量r中

③判斷余數r是否為O，若余數為O，則輸出結果；否則更新被除數和余數：m=n，n=r，并轉向第②步執行，如此循環，直至得到結果為止。