147°

最大公约数

最大公约数定义

最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b] 具体详见百度百科https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin

1. 解法之:辗转相除法

辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数https://baike.baidu.com/item/%E8%BE%97%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95/4625352

基本原理

两个数的最大公约数是指能同时整除它们的最大正整数。 设两数为a、b(a≥b),求a和b最大公约数的步骤如下: (1)用a除以b(a≥b),得a/b=q....r1(0<=r1) (2)若r1=0,则(a,b)=b; (3)若r1<>0,则再用b除以r1,得b/r1=q....r2(0<=r2). (4)若r2=0,则(a,b)=r1;若r2<>0,则继续用r1除以r2,......,如此下去,直到能整除为止。 其最后一个余数为0的除数即为(a,b)的最大公约数

辗转相除法->递归

def gcd_recur(x,y):
    print(x,y)
    if y==0:       
        return x
    else:   
        return gcd_recur (y,x%y)
       
#调用函数        
gcd_1=gcd_recur(123456,7890)
print("Result is ->>",gcd_1)

辗转相除法->迭代

def gcd_iter(x,y):   
    while x%y!=0:       
        tmp=x
        x=y
        y=tmp%y
        print(x,y)
    return y
       
#调用函数        
gcd_2=gcd_iter(123456,7890)
print("->",gcd_2)

本文由【t】发布于开源中国,原文链接:https://my.oschina.net/tedzheng/blog/2978979

全部评论: 0

    我有话说: