Question

设计一个算法，求840与1 764的最大公约数.

Answer 1

解析：可根据对自然数进行素因数分解的方法.首先对这两个数分别进行素因数分解：

840=2³×3×5×7，1 764=2²×3²×7².再确定它们的公共素因数：2，3，7.

最后确定公共素因数的指数：2²，3，7.所以840与1 764的最大公约数为2²×3×7=84.

算法步骤用自然语言描述如下：

S1  将840进行素因数分解：

840=2³×3×5×7；

S2  将1 764进行素因数分解：

1 764=2²×3²×7²；

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

S4  确定它们的公共素因数的指数：2²，3，7；

S5  最大公约数为2²×3×7=84.