我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Python求最大公约数的五种常见方法

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Python求最大公约数的五种常见方法

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

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

方法一:短除法

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

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

a=int(input("please input the first number:"))b=int(input("please input the second number:"))m,n=a,b #  创建两个变量存储a和bt=1 #  创建t作为最大公约数的载体for i in range(2,min(a,b)):    while (a%i==0 and b%i==0):       t*=i #  所有公约数累乘起来       a/=i       b/=iprint((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%nwhile t!=0:    m,n=n,t #  仔细观察不难发现:每个除式的m、n是都是上一个式子的n和余数    t=m%n #  更新余数print(f"{a}和{b}的最大公约数为{n}")

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

def GCD(a,b):    #  比较大小,保证大数除以小数    if a

方法三:更相减损术

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

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

白话文译文:

(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用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)#  判断两数是否都是偶数,如果都是偶数就同时除2while m%2==0 and n%2==0:    m,n=m/2,n/2t=m-n#  判断条件是减数和差相等while n!=t:    m,n=max(n,t),min(n,t) #  每减一轮之后,都要重新判断减数和差的大小,再次以大数减去小数    t=m-nprint(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}")

以上就是小编总结的五种常用方法了,希望对各位有所帮助!记得点赞喔!

来源地址:https://blog.csdn.net/m0_69265664/article/details/125708828

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Python求最大公约数的五种常见方法

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

java求最大公约数与最小公倍数的方法示例

本文实例讲述了java求最大公约数与最小公倍数的方法。分享给大家供大家参考,具体如下:Gongyueshu.java文件:package math;public class Gongyueshu{ public static void m
2023-05-30

C语言求最大公约数的方法有哪些

C语言求最大公约数的方法有以下几种:1. 辗转相除法:即用较大的数除以较小的数,然后用余数代替较大的数,再用较小的数除以余数,直到余数为0为止,此时较小的数即为最大公约数。```cint gcd(int a, int b) {if (b =
2023-08-12

Python使用穷举法求两个数的最大公约数问题

这篇文章主要介绍了Python使用穷举法求两个数的最大公约数问题,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
2022-12-20

怎么使用python辗转相除法求最大公约数和最小公倍数

本文小编为大家详细介绍“怎么使用python辗转相除法求最大公约数和最小公倍数”,内容详细,步骤清晰,细节处理妥当,希望这篇“怎么使用python辗转相除法求最大公约数和最小公倍数”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来
2023-07-02

C语言实现求最大公约数的方法有哪些

这篇文章主要介绍C语言实现求最大公约数的方法有哪些,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!题目描述求任意两个正整数的最大公约数问题分析最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个
2023-06-22

C语言中求最大公约数的算法探究

C语言中求最大公约数的算法探究引言:最大公约数(Greatest Common Divisor,简称GCD)是数学中常见的概念,指的是两个或更多个整数公有的最大约数。在计算机科学中,求最大公约数是一种常见的需求。本文将探究C语言中求最大公
C语言中求最大公约数的算法探究
2024-02-23

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录