求最大公约数的方法及原理?

问题描述:

求最大公约数的方法及原理?

方法一:短除法把两个数一直除以它们的公约数,取它们的商继续除,直到无约数可除为止.然后把约数全部乘起来,即为最大公约数.例:求12与48的最大公约数.所以12和48的最大公约数是 2×2×3=12方法二:欧几里德算法(辗...