最大公约数与最小公倍数的问题

发表于 | 分类于 | 阅读次数

问题描述

本篇包含如下问题：

  1. 两个非负整数的最大公约数问题
  2. 两个非负整数的最小公倍数问题
  3. n个非负整数的最大公约数问题
  4. n个非负整数的最小公倍数问题
  5. 大数的处理

预备知识

定义
最大公约数：指两个或多个整数共有约数中最大的一个
最小公倍数：两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数

辗转相除法(欧几里德算法)
两个数q，p
第一步：如果q==0，最大公约数为p；如果p==0，最大公约数为q
第二步：q对p取余，余数赋值给r，将p赋值给q，r赋值给p
(第二步的结果一定满足q大于p)
第三步：回到第一步

更相减损法
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，获取差，即为等数。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

stein算法
设置A1=A、B1=B和C1=1
1、如果An=0，BnCn是最大公约数，算法结束
2、如果Bn=0，AnCn是最大公约数，算法结束
3、如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
4、如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn (很显然啦，2不是奇数的约数)
5、如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn (很显然啦，2不是奇数的约数)
6、如果An和Bn都不是偶数，则An+1=|An-Bn|，Bn+1=min(An,Bn)，Cn+1=Cn
7、n加1，转步骤1

两个数的最小公倍数
两个数的最小公倍数等于两个数的乘积除以两个数的最大公约数

参考： 百度百科

具体实现

两个非负整数的最大公约数问题

使用辗转相除法：

1
2
3
4
5
def gcd(p,q):
    r=p%q
    if r==0:
        return q
    return gcd(q,r)

两个非负整数的最小公倍数问题

先求最大公约数，然后两数之积除以最大公约数求得

1
2
def lcm(p,q):
    return p*q/gcd(p,q)

n个非负整数的最大公约数问题

百度百科上有提到先求两个数的最大公约数，然后将这个公约数继续与第三个数求最大公约数，一直循环直到最后一个，变为这n个数的最大公约数。

1
2
3
4
5
def ngcd(list):
    if len(list)==1:
        return list[0]
    list[1]=gcd(list[0],list[1])
    return ngcd(list[1:])

n个非负整数的最小公倍数问题

同上，先求两个数的最小公倍数，再将这个最小公倍数与第三个数求最小公倍数，直至最后一个…

1
2
3
4
5
def nlcm(list):
    if len(list)==1:
        return list[0]
    list[1]=lcm(list[0],list[1])
    return nlcm(list[1:])

大数的处理

int型数据是4个字节，long型在64位系统下是8字节，因此对于一个无法用8字节表示的数使用除法和取模会很复杂，于是就有了上面的stein算法，其本质就是更相减损法，只是多了下面一条：
“对于一个偶数A和一个奇数B，若有 $A/(2^k)=M$ ，且M，k均为整数，则A和B的最大公约数即为M和B的最大公约数”
这个可以使用前面的辗转相除法证明

如果觉得有帮助，给我打赏吧！