Python辗转相除法代码,辗转相除法的算法步骤python

　　用除法求两个数的最大公约数的步骤如下。

　　首先，用较小的数除以较大的数，得到第一个余数；

　　将较小的数除以第一个余数，得到第二个余数；

　　将第一余数除以第二余数以获得第三余数；

　　这样，在最后一个余数变成0之前，依次把最后一个余数去掉。的最后一个除数是最大公约数(如果最后一个除数是1，则原来的两个数是质数)。

　　例如，找出1515和600最大公约数，

　　第一次：1515除以600，商是2，剩下315；

　　第二批：600除以315，1的商剩余285；

　　第三轮：315除以285，商是1/30；

　　第四批：285除以30，商9剩余15；

　　第五套：15除以30，商是2比0多。

　　55和600的最大公约数是15。

　　辗转相除是求两个数的最大公约数的方法。求几个数的最大公约数，先求两个数的最大公约数，再求第三个数的最大公约数。依次进行到最后一个数字。最后一个最大公约数是几个数的最大公约数。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。