辗转相除法，辗转相减法，枚举法实现最大公约数的计算 && 求最小公倍数

今天药忘吃喽~ 2022-04-23 23:10 213阅读 0赞

**题目：最大公约数和最小公倍数计算。**

**从键盘接收两个整数，编写程序求出这两个整数的最大公约数和最小公倍数**

**(提示:求最大公约数可用辗转相除法，求最小公倍数的积除以最大公约数即可)。**

**这里分别列举辗转相除法，辗转相减法，枚举法三种方法来求最大公约数。**

**而最小公倍数  =  两个整数的乘积 /  最大公约数。**

**gcd函数代表求最大公约数，lcm代表求最小公倍数。**

### 1、辗转相除法 ###

### 思路 ###

1.将两整数求余 u%v = x

2.如果x = 0, 则 v为最大公约数

3.如果x != 0, 则 u=v；v=x；继续从1开始执行

4.也就是说该循环的是否继续的判断条件就是x是否为0

### 流程图 ###

![70][]

### 实现代码 ###

# -*- coding:utf-8 -*-
    def gcd(u,v):
        #辗转相除法
        x=u%v
        while x!=0:
            u=v
            v=x
            x=u%v
        return v
    
    def lcm(u,v,h):
        return u*v/h
    
    u = int(input("请输入第一个整数："))
    v = int(input("请输入第二个整数："))
    h = gcd(u,v)
    print("%d 和 %d 的最大公约数为: %d"%(u,v,h))
    l = lcm(u,v,h)
    print("%d 和 %d 的最小公倍数为: %d"%(u,v,l))

![20190409223954106.png][]

### 2、辗转相减法 ###

### 思路 ###

1.如果u>v，u=u-v

2.如果v>u，v=v-u

3.假如u=v，则 u或v  是最大公约数

4.如果u!=v,  则继续继续相减，直至u=v

### 流程图 ###

![20190409221509959.png][]

### 实现代码 ###

# -*- coding:utf-8 -*-
    def gcd(u,v):
        #辗转相减法
        while u!=v:
            if u>v:
                u=u-v
            else:
                v=v-u
        return v
    
    def lcm(u,v,h):
        return u*v/h
    
    u = int(input("请输入第一个整数："))
    v = int(input("请输入第二个整数："))
    h = gcd(u,v)
    print("%d 和 %d 的最大公约数为: %d"%(u,v,h))
    l = lcm(u,v,h)
    print("%d 和 %d 的最小公倍数为: %d"%(u,v,l))

### 3、枚举法 ###

### 思路 ###

1.选出u，v中最小的一个数字放到min中

2.分别用u，v对i求余数，即看是否能被整除

3.直到u，v同时都能被i整除

4.如不能整除，i加一 继续开始执行，直到i等于min

### 流程图 ###

![70 1][]

### 实现代码 ###

# -*- coding:utf-8 -*-
    def gcd(u,v):
        # 枚举法
        if u<v:
            min=u
        else:
            min=v
    
        i=1
        while i<min:
            if u%i == 0:
                if v%i == 0:
                    x=i
            i+=1
        return x
    
    def lcm(u,v,h):
        return u*v/h
    
    u = int(input("请输入第一个整数："))
    v = int(input("请输入第二个整数："))
    h = gcd(u,v)
    print("%d 和 %d 的最大公约数为: %d"%(u,v,h))
    l = lcm(u,v,h)
    print("%d 和 %d 的最小公倍数为: %d"%(u,v,l))

--------------------

**参考文章：**

[https://blog.csdn.net/yancelyq/article/details/79504364][https_blog.csdn.net_yancelyq_article_details_79504364]

[https://blog.csdn.net/jackfjw/article/details/82469300][https_blog.csdn.net_jackfjw_article_details_82469300]

[70]: /images/20220222/bf0162b69210475cb24e2d7067f1ab2a.png
[20190409223954106.png]: /images/20220222/7be290aed96248b694b67c4e00c7b6d6.png
[20190409221509959.png]: /images/20220222/4260d97d762a4082a39022a042bfe469.png
[70 1]: /images/20220222/4b28fc1880bd407dab8a4fc7823b9410.png
[https_blog.csdn.net_yancelyq_article_details_79504364]: https://blog.csdn.net/yancelyq/article/details/79504364
[https_blog.csdn.net_jackfjw_article_details_82469300]: https://blog.csdn.net/jackfjw/article/details/82469300