怎样最快找出两个数的最大公因数
发布网友
发布时间：2022-04-23 06:08
共1个回答
热心网友
时间：2023-08-10 06:46
怎样最快找出两个数的最大公因数
有一种叫辗转相除法
两个整数的最大公约数等于“其中较小的数”和“两数的差”的最大公约数.
例如,252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；
因为两数之差252 − 105 = 147,
147和105的最大公约数是21.所以252和105的最大公约数是21.
还可以继续辗转下去.
147和105的最大公约数就是
147-105=42与105的最大公约数
继续辗转
42与105的最大公约数就是
105-42=63与42的最大公约数,这是很明显就看出是21 了
