怎么求最大公因数

畅饮敌敌畏 3年前已收到1个回答举报

共回答了428个问题采纳率：96.5% 评论

列举法

假设要求两个数的公因数，可以分别列举出这两个数的所有因数，再寻找相同的因数（公因数），其中最大的就是最大公因数。

例如：

求24和36的最大公因数，

24的因数:1，2，3，4，6，8，12，24；

36的因数:1，2，3，4，6，9，12，18，36；

24和36的公因数有1，2，3，4，6，12；其中最大的是12。

所以12就是24和36的最大公因数。

辗转相除法（欧几里得算法）

辗转相除法是先用两个数中较大的数除以较小的数，如果有余数，则用较小的那个数继续除以余数，按照这样的方法一直除下去，除到余数为0为止，那么最后的除数就是两个数的最大公因数。

例如，求319和377的最大公因数：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

3小时前

可能相似的问题

猜你喜欢的问题

热门问题推荐