辗转相除法求三个数的最大公约数_辗转相除

来源:互联网 时间:2023-07-06 07:45:52


(资料图)

1、辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。

2、它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。

3、如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

4、另一种求两数的最大公约数的方法是更相减损法。

5、扩展资料:辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公约数的:若 r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)2、a 和其倍数之最大公约数为 a。

6、另一种写法是:a ÷ b,令r为所得余数(0≤r

7、2、互换:置 a←b,b←r,并返回第一步。

8、参考资料来源:百度百科——辗转相除法。

本文到此分享完毕,希望对大家有所帮助。

关键词:

推荐内容

Copyright 2000-2021 by www.jiaoyu.rexun.cn all rights reserved

备案号:豫ICP备20005723号-6

邮箱 : 29 59 11 57 8@qq.com