辗转相除法(算法步骤)

辗转相除法的算法步骤为,两个数中用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。得到最后的除数就是这两个数的最大公约数。

辗转相除法(算法步骤)
辗转相除法,又名欧几里德算法,是求最大公约数的一种方法。以除数和余数反复做除法运算,最终当余数为0时,取当前算式除数为最大公约数。算法举例:
1997/615=3(余152)
615/152=4(余7)
152/7=21(余5)
7/5=1(余2)
5/2=2(余1)
2/1=2(余0)
至此,得出1997和615的最大公约数为1。

联系我们

000-000-8888

在线咨询:点击这里给我发消息

邮件:

工作时间:周一至周五,9:30-18:30,节假日休息