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的最大公因数为：．