Question

設計一個算法．求84與1764的最大公因數．

Answer 1

答案：略
解析：

解：算法步驟如下： (1)先將84進行素因數分解：； (2)將1764進行素因數分解：； (3)確定它們的公共素因數：2，3，7； (4)確定公共素因數的指數，公共素因數2，3，7的指數分別是2，1，1； (5)最大公因數為．

提示：

根據對自然數素因數分解的方法來設計算法，可以按以下思路進行． 首先，對兩數分別進行素因數分解：，． 其次，確定兩數的公共素因數：2，3，7． 最后，確定公共素因數的指數：對于公共素因數2，是1764的因數，是84的因數，因此是這兩個數的公因數，這樣就確定了公共素因數2的指數為2．同樣可以確定出公因數3和7的指數均為1．這樣，就確定了84與1764的最大公因數為：．