Question

設(shè)計(jì)一個(gè)算法，求840與1 764的最大公約數(shù).

Answer 1

解析：可根據(jù)對(duì)自然數(shù)進(jìn)行素因數(shù)分解的方法.首先對(duì)這兩個(gè)數(shù)分別進(jìn)行素因數(shù)分解：

840=2³×3×5×7，1 764=2²×3²×7².再確定它們的公共素因數(shù)：2，3，7.

最后確定公共素因數(shù)的指數(shù)：2²，3，7.所以840與1 764的最大公約數(shù)為2²×3×7=84.

算法步驟用自然語(yǔ)言描述如下：

S1  將840進(jìn)行素因數(shù)分解：

840=2³×3×5×7；

S2  將1 764進(jìn)行素因數(shù)分解：

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

S3  確定它們的公共素因數(shù)：2，3，7；

S4  確定它們的公共素因數(shù)的指數(shù)：2²，3，7；

S5  最大公約數(shù)為2²×3×7=84.