算法思想:
首先给定两个数a,b(a>b),则根据除法运算,a/b=q…r。q是商,r是余数。也可以表示为a=bq+r。这是小学就知道的。
下面给出一个定理:
若a=bq+r,则(a,b)=(b,r),即a,b的最大公约数等于b,r的最大公约数。
举个例子来说:
24=10*2+4,那么(24,10)=(10,4)=2
这个定理的证明也很简单。
设c是a和b的任意一个公约数,则c能同时整除a和b,即a=cx,b=cy,(x,y是整数)
将它们代入“a=bq+r”中:
cx=cyq+r
得到r=c(x-yq),说明c也能整除r,即c也是b和r的公约数。
于是a和b的公约数就是b和r的公约数,那么a和b最大公约数就是b和r的最大公约数,(a,b)=(b,r)。
定理得证。
欧几里德算法就是对照这个定理来做的,每一次辗转相除其实就是用了一次上面的定理,一步一步递推得到最后结果。
辗转相除法:
(1)比较两数,并使m>n
(2)将m作被除数,n做除数,相除后余数为r
(3)循环判断r,若r==0,则n为最大公约数,结束循环。若r !=0 ,执行m=n,n=r;将m作被除数,n做除数,相除后余数为r
运行代码如下:
num1 = int(input("请输入第一个数字:"))
num2 = int(input("请输入第一个数字:"))
m = max(num1, num2)
n = min(num1, num2)
r = m % n
while r != 0:
m = n
n = r
r = m % n
print(num1, "和", num2, "的最大公约数为", n)