Question

设计一个算法，求出840与1764的最大公因数.

Answer 1

同解析

解析:

我们已经学习过了对自然数的素因数分解的方法，下面的算法就是在此基础上设计的.

解题思路如下：

首先对两个数进行素因数分解：

840=2³×3×5×7，1764=2²×3²×7²_，

其次，确定两个数的公共素因数：2，3，7.

接着确定公共素因数的指数：对于公共素因数2，840中为2³，1764中为2²，应取较少的一个2²，同理可得下面的因数为3和7.

算法步骤：

第一步：将840进行素数分解2³×3×5×7；

第二步：将1764进行素数分解2²×3²×7²；

第三步：确定它们的公共素因数：2，3，7；

第四步：确定公共素因数2，3，7的指数分别是：2，1，1；

第五步：最大公因数为2²×3¹×7¹=84.

点评：质数是除１以外只能被１和本身整除的正整数，它应该是无限多个，但是目前没有一个规律来确定所有的质数。