Question

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

Answer 1

答案：略
解析：

解：算法步驟如下： (1)先將84進(jìn)行素因數(shù)分解：； (2)將1764進(jìn)行素因數(shù)分解：； (3)確定它們的公共素因數(shù)：2，3，7； (4)確定公共素因數(shù)的指數(shù)，公共素因數(shù)2，3，7的指數(shù)分別是2，1，1； (5)最大公因數(shù)為． 以上步驟就是求兩個正整數(shù)的最大公因數(shù)的一個算法．這個算法的思想具有一般性，它可以幫助設(shè)計(jì)者求三個或者三個以上正整數(shù)的最大公因數(shù)．在這個算法的設(shè)計(jì)中，對自然數(shù)進(jìn)行素因數(shù)分解是基礎(chǔ)，是解決這個問題的“平臺”；同樣，求兩個非零自然數(shù)的最大公因數(shù)的算法，也可以成為解決其他問題的“平臺”．“平臺”的思想在算法設(shè)計(jì)中是一個最基本的思想，也是數(shù)學(xué)中思考問題的一個重要思想．

提示：

根據(jù)對自然數(shù)素因數(shù)分解的方法來設(shè)計(jì)算法，可以按以下思路進(jìn)行． 首先，對兩數(shù)分別進(jìn)行素因數(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ù)為：．