Python实现求两数最大公约数(四种方法)

最新推荐文章于 2025-03-14 09:07:34 发布

@阿证1024

最新推荐文章于 2025-03-14 09:07:34 发布

阅读量1.6w

点赞数 21

分类专栏： Python

本文链接：https://blog.csdn.net/qq_43437122/article/details/103516887

版权

Python 专栏收录该内容

17 篇文章

订阅专栏

本文介绍了四种不同的算法来寻找两个整数的最大公约数：辗转相除法（使用while循环和递归实现）、辗转相减法及枚举法。每种方法都有其特点，如辗转相除法的递归实现简洁但可能在大数下效率降低。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1. 辗转相除法(while循环实现)

(1) 两数求余temp = p % q
(2) temp = 0时，q为最大公约数
(3) temp !=0时，p = q；q = temp注：该循环的是否继续的判断条件就是temp是否为0

def fuc(p, q):
    temp = p % q
    while temp!=0:
        p = q
        temp = p
        q = temp % q
    return q

2.辗转相减法

(1) 如果p > q ，p = p - q
(2) 如果q > p ，q = q - p
(3) 假如p = q ，则 p或q 是最大公约数
(4) 如果p != q,则继续继续相减，直至p = q

def fuc2(p, q):
    while p!=q:
        if p>q:
            p = p - q
        else:
            q = q - p
    return p

3. 枚举法

(1) 将两数p，q中最小的放到smaller中
(2) 用p，q分别对i（1到smaller之间）求余数，看是否能被整除
(3) 直到p，q同时被i整除
(4) 如不能整除，i+1后继续，直到i等于smaller

def fuc3(p, q):
    if p>q:
        smaller = q
    else:
        smaller = p
    for i in range(1, smaller+1):
        if (p%i == 0) and (q%i == 0):
            ret = i    
    return ret

4.欧几里得算法（辗转相除的递归实现）

该方法其实就是辗转相除法的递归版本实现
(1) 如果q=0，返回p；判断p>q
(2) 如果p>q，则p、q的最大公约数等于q与p%q的最大公约数，以此递归

def fuc4(p, q):
    if q == 0:
        return p
    return fuc4(q, p % q)

第四种方法是不是代码最少，可以说是极简版，而且性能适中。但是当p,q数值较大时，递归效率效率可能就不太占优势了。