如何求两个数的所有公约数

liuzaping 1年前他留下的回答 已收到1个回答

我太有才呢 春芽

该名网友总共回答了11个问题，此问答他的回答如下：采纳率：90.9%

把两个数分别写成质数相乘的形式,比如求24和36的公约数,24＝2×2×2×3,
36＝2×2×3×3,
则重复的三个数(2,2,3)从其中挑选的任意数量的数字相乘的结果都是他们的公约数.有2,3,4,6,12.

1年前他留下的回答 追问

5

liuzaping

我想把它编写成一个程序，能够循环计算的，就像求两个数的最大公约数那样能够依次用大数除以小数那种类似的方法。
适合于任意数的算法，不想用穷举法来算，不好编程啊
能帮我想到吗？？？

我太有才呢

那只能先用你上面的辗转相除法求出最大公约数，然后对最大公约数与小于等于他一半大小的数相除，能整除的数还有商都是它的约数。(所有的公约数都在最大公约数之中)

liuzaping

真是太感谢了，所有公约数果然在最大公约数中。

　　以上就是小编为大家介绍的如何求两个数的所有公约数 的全部内容，如果大家还对相关的内容感兴趣，请持续关注上海建站网！