首页 > 编程 > Python > 正文

python求两个数字的最大公约数(辗转相除法)

2019-11-08 18:45:31
字体:
来源:转载
供稿:网友
def gcd(a,b):    while b:        r = a%b        a = b        b = r    return a PRint(gcd(15,25))

辗转相除法介绍:

设两数为a、b(a>b),求a和b最大公约数(a,b)的步骤如下:用a除以b,得a÷b=q......r1(0≤r1)。若r1=0,则(a,b)=b;若r1≠0,则再用b除以r1,得b÷r1=q......r2 (0≤r2).若r2=0,则(a,b)=r1,若r2≠0,则继续用r1除以r2,……如此下去,直到能整除为止。其最后一个为被除数的余数的除数即为(a, b)。


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表