Python实现求解最大公约数的五种方法总结

目录
  • 方法一:短除法
  • 方法二:欧几里得算法(辗转相除法)
  • 方法三:更相减损术
  • 方法四:穷举法(枚举法)
  • 方法五:Stein算法

求最大公约数是习题中比较常见的类型,下面小编会给大家提供五种比较常见的算法,记得帮忙点个赞哦!

一般来说,最大公约数的求法大概有5种

方法一:短除法

短除法是求最大公因数的一种方法,也可用来求最小公倍数。求几个数最大公因数的方法,开始时用观察比较的方法,即:先把每个数的因数找出来,然后再找出公因数,最后在公因数中找出最大公因数。后来,使用分解质因数法来分别分解两个数的因数,再进行运算。之后又演变为短除法。短除法运算方法是先用一个除数除以能被它除尽的一个质数,以此类推,除到两个数的商是互质数为止。

简单来说就是逐步找出两个数的所有公约数,再将这些公约数累乘起来,就能得到最大公约数啦!

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
m,n=a,b #  创建两个变量存储a和b
t=1 #  创建t作为最大公约数的载体
for i in range(2,min(a,b)):
    while (a%i==0 and b%i==0):
       t*=i #  所有公约数累乘起来
       a/=i
       b/=i
print((f"{m},{n}的最大公约数为:{t}"))

这种方法虽然有点麻烦,但是逻辑却很清楚,不容易出错。

方法二:欧几里得算法(辗转相除法)

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法,是这样进行的:

1997 / 615 = 3······152

615 / 152 = 4······7

152 / 7 = 21······5

7 / 5 = 1······2

5 / 2 = 2······1

2 / 1 = 2······0

至此,最大公约数为1

以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。

明白了这其中的逻辑,我们就可以着手开始写程序啦!

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
#  首先要给两数排序,保证大数除以小数
m=max(a,b)
n=min(a,b)
t=m%n
while t!=0:
    m,n=n,t #  仔细观察不难发现:每个除式的m、n是都是上一个式子的n和余数
    t=m%n #  更新余数
print(f"{a}和{b}的最大公约数为{n}")

当然了,递归方法也能实现欧几里得算法。

def GCD(a,b):
    #  比较大小,保证大数除以小数
    if a<b:
        a,b=b,a
    #  判断是否能整除,若能整除,直接返回被除数
    if a%b==0:
        return b
    #  若不能整除,则返回函数GCD,参数做相应变化
    else:
        return GCD(b,a%b)
a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
gcd=GCD(a,b)
print(f"{a}和{b}的最大公约数为{gcd}")

方法三:更相减损术

更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。原文是:

可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

白话文译文:

(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。

具体步骤:

第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。

第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”,就是公约数。求“等数”的办法是“更相减损”法。

现在使用更相减损术求98与63的最大公约数。

解:由于63不是偶数,把98和63以大数减小数,并辗转相减:

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以,98和63的最大公约数等于7。

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
#  首先要给两数排序,保证大数减小数
m=max(a,b)
n=min(a,b)
#  判断两数是否都是偶数,如果都是偶数就同时除2
while m%2==0 and n%2==0:
    m,n=m/2,n/2
t=m-n
#  判断条件是减数和差相等
while n!=t:
    m,n=max(n,t),min(n,t) #  每减一轮之后,都要重新判断减数和差的大小,再次以大数减去小数
    t=m-n
print(f"{a}和{b}的最大公约数为{n}")

方法四:穷举法(枚举法)

从两个数中较小数开始,由小到大列举,找出公约数并保证该公约数也属于较大数,这些公约数的最大者就是最大公约数;也可以从大到小列举,直到找出公约数后跳出循环,该公约数即是最大公约数。

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
p,q=min(a,b),max(a,b)
lst=[]
for i in range(1,p+1):
    if p%i==0 and q%i==0:
        lst.append(i)
gcd=max(lst)
print(f"{a}和{b}的最大公约数为{gcd}")

#a=int(input("please input the first number:"))
#b=int(input("please input the second number:"))
#p,q=min(a,b),max(a,b)
#gcd=0
#for i in range(p,0,-1):
#    if p%i==0 and q%i==0:
#        gcd=i
#        break
#print(f"{a}和{b}的最大公约数为{gcd}")

方法五:Stein算法

Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。

欧几里得算法缺陷:

欧几里德算法是计算两个数最大公约数的传统算法,无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷,这个缺陷在素数比较小的时候一般是感觉不到的,只有在大素数时才会显现出来。

一般实际应用中的整数很少会超过64位(当然已经允许128位了),对于这样的整数,计算两个数之间的模是很简单的。对于字长为32位的平台,计算两个不超过32位的整数的模,只需要一个指令周期,而计算64位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过64位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多CPU时间。对于现代密码算法,要求计算128位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模。

看下面两个结论:

gcd(a,a)=a,也就是一个数和其自身的公约数仍是其自身。

gcd(ka,kb)=k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换。特殊地,当k=2时,说明两个偶数的最大公约数必然能被2整除。

当k与b互为质数,gcd(ka,b)=gcd(a,b),也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地,当k=2时,说明计算一个偶数 和一个奇数的最大公约数时,可以先将偶数除以2。

:param a: 第一个数

:param b: 第二个数

:return: 最大公约数

def gcd_Stein(a, b):
    #  保证b比a小
    if a < b:
        a, b = b, a
    if (0 == b):
        return a
    #  a、b都是偶数,除2右移一位即可
    if a % 2 == 0 and b % 2 == 0:
        return 2 * gcd_Stein(a / 2, b / 2)
    #  a是偶数
    if a % 2 == 0:
        return gcd_Stein(a / 2, b)
    #  b是偶数
    if b % 2 == 0:
        return gcd_Stein(a, b / 2)
    #  都是奇数
    return gcd_Stein((a + b) / 2, (a - b) / 2)

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
gcd=int(gcd_Stein(a,b))
print(f"{a}和{b}的最大公约数为{gcd}")

以上就是Python实现求解最大公约数的五种方法总结的详细内容,更多关于Python求最大公约数的资料请关注我们其它相关文章!

(0)

相关推荐

  • 使用Python求解最大公约数的实现方法

    1. 欧几里德算法 欧几里德算法又称辗转相除法, 用于计算两个整数a, b的最大公约数.其计算原理依赖于下面的定理: 定理: gcd(a, b) = gcd(b, a mod b) 证明:   a可以表示成a = kb + r, 则r = a mod b   假设d是a, b的一个公约数, 则有  d|a, d|b, 而r = a - kb, 因此d|r.   因此,d是(b, a mod b)的公约数.   加上d是(b,a mod b)的公约数,则d|b, d|r, 但是a = kb + r

  • Python基于更相减损术实现求解最大公约数的方法

    本文实例讲述了Python基于更相减损术实现求解最大公约数的方法.分享给大家供大家参考,具体如下: 先从网上摘录一段算法的描述如下: 更相减损法:也叫 更相减损术,是出自< 九章算术>的一种求最大公约数的算法,它原本是为 约分而设计的,但它适用于任何需要求最大公约数的场合. <九章算术>是中国古代的数学专著,其中的"更相减损术"可以用来求两个数的最大公约数,即"可半者半之,不可半者,副置分母.子之数,以少减多,更相减损,求其等也.以等数约之."

  • Python实现的求解最大公约数算法示例

    本文实例讲述了Python实现的求解最大公约数算法.分享给大家供大家参考,具体如下: 使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式.其实,我写分解质因式程序的时候就是因为发现在实现最大公约数求解的过程中用到了这个功能. 比较令我开心的是之前学的一点Python集合处理功能居然在这个时候也派上了用场,小程序的完成让人感觉比较舒心. 代码实现如下: #!/usr/bin/python from collections import Counter def PrimeNum(

  • python求最大公约数和最小公倍数的简单方法

    python怎么求最大公约数和最小公倍数 一.求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数.比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数. 具体代码如下: def gongyue(a, b): """ 欧几里得算法----辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 "

  • python如何求解两数的最大公约数

    题目: 给定两个自然数,求这两个数的最大公约数. 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个. 但是这样做有几个缺点:一是做除法计算量比较大,二是遍历所有自然数完全没有必要.另外,如果能够循环,还是不要递归,因为Python的函数递归最大栈空间是1000(如果我没有记错的话),如果数字大一些,很容易出现爆栈. 所以在这里有两种处理方法: 1.如果较大的自然数除较小的一个自然数,取得余数,较小的自然数和余数的最大公约

  • Python基于辗转相除法求解最大公约数的方法示例

    本文实例讲述了Python基于辗转相除法求解最大公约数的方法.分享给大家供大家参考,具体如下: 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数. 这个题目我最初的理解理解错了,自然也没有做出标准答案.现在按照标准答案的解答写一下相应的代码实现: # -*- coding:utf-8 -*- #! python2 def MaxCommDivisor(m,n): while m * n != 0: m = m % n if m == 0

  • Python实现求解最大公约数的五种方法总结

    目录 方法一:短除法 方法二:欧几里得算法(辗转相除法) 方法三:更相减损术 方法四:穷举法(枚举法) 方法五:Stein算法 求最大公约数是习题中比较常见的类型,下面小编会给大家提供五种比较常见的算法,记得帮忙点个赞哦! 一般来说,最大公约数的求法大概有5种 方法一:短除法 短除法是求最大公因数的一种方法,也可用来求最小公倍数.求几个数最大公因数的方法,开始时用观察比较的方法,即:先把每个数的因数找出来,然后再找出公因数,最后在公因数中找出最大公因数.后来,使用分解质因数法来分别分解两个数的因

  • python中调试或排错的五种方法示例

    前言 本文主要给大家介绍了关于python中调试或排错的五种方法,分享出来供大家参考学习,下面话不多说了,来一起看看详细的的介绍吧 python调试或排错的五种方法 1.print,直接打印,比较简单而且粗暴 在代码中直接输入print+需要输出的结果,根据打印的内容判断即可 2.assert断言,很方便,测试人员常常在写自动化用例的时候用的比较多 如下,直接将预期结果和实际结果做判断 def true_code(): x = 3 y = 2 z = x + y assert(5==z), "z

  • 教你利用Python玩转histogram直方图的五种方法

    直方图 直方图是一个可以快速展示数据概率分布的工具,直观易于理解,并深受数据爱好者的喜爱.大家平时可能见到最多就是 matplotlib,seaborn 等高级封装的库包,类似以下这样的绘图. 本篇博主将要总结一下使用Python绘制直方图的所有方法,大致可分为三大类(详细划分是五类,参照文末总结): 纯Python实现直方图,不使用任何第三方库 使用Numpy来创建直方图总结数据 使用matplotlib,pandas,seaborn绘制直方图 下面,我们来逐一介绍每种方法的来龙去脉. 纯Py

  • 详解python解压压缩包的五种方法

    这里讨论使用Python解压例如以下五种压缩文件: .gz .tar  .tgz .zip .rar 简单介绍 gz: 即gzip.通常仅仅能压缩一个文件.与tar结合起来就能够实现先打包,再压缩. tar: linux系统下的打包工具.仅仅打包.不压缩 tgz:即tar.gz.先用tar打包,然后再用gz压缩得到的文件 zip: 不同于gzip.尽管使用相似的算法,能够打包压缩多个文件.只是分别压缩文件.压缩率低于tar. rar:打包压缩文件.最初用于DOS,基于window操作系统. 压缩

  • Python 字符串去除空格的五种方法

    在处理Python代码字符串的时候,我们常会遇到要去除空格的情况,所以就总结了多种方法供大家参考. 1.strip()方法 去除字符串开头或者结尾的空格 str = " Hello world " str.strip() 输出: "Hello world" 2.lstrip()方法 去除字符串开头的空格 str = " Hello world " str.lstrip() 输出: 'Hello world ' 3.rstrip()方法 去除字符串

  • Python中移除List重复项的五种方法

    本文列些处几种去除在Python 列表中(list)可能存在的重复项,这在很多应用程序中都会遇到的需求,作为程序员最好了解其中的几种方法 以备在用到时能够写出有效的程序. 方法1:朴素方法 这种方式是在遍历整个list的基础上,将第一个出现的元素添加在新的列表中. 示例代码: # Python 3 code to demonstrate # removing duplicated from list # using naive methods # initializing list test_l

  • python 模块重载的五种方法

    环境准备 新建一个 foo 文件夹,其下包含一个 bar.py 文件 $ tree foo foo └── bar.py 0 directories, 1 file bar.py 的内容非常简单,只写了个 print 语句 print("successful to be imported") 只要 bar.py 被导入一次,就被执行一次 print 禁止重复导入 由于有 sys.modules 的存在,当你导入一个已导入的模块时,实际上是没有效果的. >>> from

  • python b站视频下载的五种版本

    项目地址: https://github.com/Henryhaohao/Bilibili_video_download 介绍 对于单P视频:直接传入B站av号或者视频链接地址(eg: 49842011或者https://www.bilibili.com/video/av49842011) 对于多P视频: 1.下载全集:直接传入B站av号或者视频链接地址(eg: 49842011或者https://www.bilibili.com/video/av49842011) 2.下载其中一集:传入那一集

  • Python格式化输出字符串的五种方法总结

    目录 1. 引言 2. 函数 center() 3. 函数 ljust() 4. 函数 rjust() 5. 函数 zfill() 6. 函数 title() 7. 使用 1. 引言 Python语言有许多优点,常用于不同的领域,如数据科学.web开发.自动化运维等.开发人员在这些技术中选择Python的一个重要原因是Python语法简单,可以节省大家的开发时间. 在本文中,我们将学习如何使用字符串中内置的方法来格式化字符串.闲话少说,我们直接开始吧! 2. 函数 center() 函数cent

  • Python实现将内容写入文件的五种方法总结

    目录 一.write()方法 二.writelines() 方法 三.print() 函数 四.使用 csv 模块 五.使用 json 模块 一.write()方法 使用 write() 方法:使用 open() 函数打开文件,然后使用 write() 方法将内容写入文件.例如: with open('example.txt', 'w') as f: f.write('Hello, world!') open() 函数是 Python 内置的用于打开文件的函数,其常用的参数及其含义如下: 1.f

随机推荐