Question

設(shè)計一個算法．求84與1764的最大公因數(shù)．

Answer 1

答案：略
解析：

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

提示：

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