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

题目：

给定两个自然数，求这两个数的最大公约数。

分析：

单看题目的话，非常简单，我们可以循环遍历自然数，如果能够整除两个自然数，就把这个数记下来，在这些记录中找到最大的一个。
但是这样做有几个缺点：一是做除法计算量比较大，二是遍历所有自然数完全没有必要。另外，如果能够循环，还是不要递归，因为Python的函数递归最大栈空间是1000（如果我没有记错的话），如果数字大一些，很容易出现爆栈。

所以在这里有两种处理方法：

1、如果较大的自然数除较小的一个自然数，取得余数，较小的自然数和余数的最大公约数就是我们要求的值。
2、如果较大的自然数减去较小的自然数，取得差值，较小的自然数和差值的最大公约数就是我们要求的值。

基于以上两条，我们就可以在根据定义得到的算法的基础上进行改进，但是！减法操作当然比取余要方便很多。而且在计算机里，做位运算的速度要比加减乘除都快，所以，我写了四个算法，具体描述在代码的 __doc__里有注释阐述

代码：

def greatest_common_divisor_1(self, num1, num2):
    '''
    数值计算寻找最大公约数，给定两个整数，计算其最大公约数，时间复杂度为 o(min(num1,num2))，取余运算复杂度高
    '''
    gbc = 1
    for i in xrange(2, min(num1, num2)+1):
      if num2 % i == 0 and num1 % i == 0:
        gbc = i
    return gbc

  def greatest_common_divisor_2(self, num1, num2):
    '''
    辗转相减法，时间复杂度最差为 o(min(num1,num2))，一般情况下都比这个要好。相减运算要比除法方便很多
    '''
    while num1 != num2:
      if num1 > num2:
        num1 = num1 - num2
      else:
        num2 = num2 - num1
    return num1

  def greatest_common_divisor_3(self, num1, num2):
    '''
    求余数法，取模运算比较麻烦，时间复杂度低 o(log max(num1, num2))
    '''
    while num1 != num2:
      if num1 > num2:
        if num1 % num2 == 0:
          return num2
        num1 = num1 % num2
      else:
        if num2 % num1 == 0:
          return num1
        num2 = num2 % num1
    return num1

  def greatest_common_divisor(self, num1, num2):
    '''
    求两个数的最大公约数
    综合取余法和辗转相减法，既能得到较好的时间复杂度，又能避免取余运算，时间复杂度稳定 o(log max(num1,num2))
    如果取两个非常大的数的话，前面的方法很容易爆栈、取余困难等等，但是该方法没有问题
    a = 999999342353200
    b = 777774234
    print greatest_common_divisor(a, b)
    '''
    factor = 1
    if num1 < num2:
      return greatest_common_divisor_1(num2, num1)
    while num1 != num2:
      if num1 & 1 is False and num2 & 1 is False: # 均为偶数
        num1 = num1 >> 1
        num2 = num2 >> 2
        factor *= 2
      elif num1 & 1 is False and num2 & 1 is True:
        num1 = num1 >> 1
      elif num1 & 1 is True and num2 & 1 is False:
        num2 = num2 >> 1
      else:
        if num1 > num2:
          num1 = num1 - num2
        else:
          num2 = num2 - num1
    return factor*num1

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

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

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

  • Python实现求最大公约数及判断素数的方法

    本文实例讲述了Python实现求最大公约数及判断素数的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num, count) break #break跳出时会跳出下面的else语句 count -= 1 else: prin

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

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

    本文实例讲述了Python基于辗转相除法求解最大公约数的方法.分享给大家供大家参考,具体如下: 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数. 这个题目我最初的理解理解错了,自然也没有做出标准答案.现在按照标准答案的解答写一下相应的代码实现: # -*- coding:utf-8 -*- #! python2 def MaxCommDivisor(m,n): while m * n != 0: m = m % n if m == 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基于递归算法求最小公倍数和最大公约数.分享给大家供大家参考,具体如下: # 最小公倍数 def lcm(a, b, c=1): if a * c % b != 0: return lcm(a, b, c+1) else: return a*c test_cases = [(4, 8), (35, 42), (5, 7), (20, 10)] for case in test_cases: print('lcm of {} is {}'.format(*case, lcm

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

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

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

  • Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python基于递归和非递归算法求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了所以就写下来作为记录,也希望帮到别人,下面是代码: #!/usr/bin/env python #coding:utf-8 from fractions import gcd #非递归实现 def gcd_test_one(a, b): if a!=0 and b!=0: if a>b: a,

  • Python实现利用最大公约数求三个正整数的最小公倍数示例

    本文实例讲述了Python实现利用最大公约数求三个正整数的最小公倍数.分享给大家供大家参考,具体如下: 在求解两个数的小公倍数的方法时,假设两个正整数分别为a.b的最小公倍数为d,最大公约数为c.存在这样的关系d=a*b/c.通过这个关系式,我们可以快速的求出三个正整数的最小公倍数. def divisor(a,b): c = a%b while c>0: a=b b=c c=a%b return b x1 = input("input1:") x2 = input("

  • Python自定义函数实现求两个数最大公约数、最小公倍数示例

    Python自定义函数实现求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python自定义函数实现求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 1. 求最小公倍数的算法: 最小公倍数  =  两个整数的乘积 /  最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: ① 整数A对整数B进行取整, 余数用整数C来表示    举例: C = A % B ② 如果C等于0,则C就是整数A和整数B的最大公约数 ③ 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2

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

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

  • Java求解两个非负整数最大公约数算法【循环法与递归法】

    Java求解两个非负整数最大公约数算法【循环法与递归法】

    本文实例讲述了Java求解两个非负整数最大公约数算法.分享给大家供大家参考,具体如下: 代码功能: 1.Java实现(完整源码附测试用例): 2.求解两个非负整数p,q(p>=q)的最大公约数: 3.循环法 以及 递归法两种求解思路: 完整源码: /* GCD:Greateast Common Divisor */ public class GCD{ public static void main(String args[]){ /* Test Case */ int p = 32; int q

  • 在Python中获取两数相除的商和余数方法

    方法一:可以使用//求取两数相除的商.%求取两数相除的余数.[/在Python中获取的是相除的结果,一般为浮点数] 方法二:使用divmod()函数,获取商和余数组成的元祖 实例代码: #!/usr/bin/python3 # -*- coding: utf-8 -*- a = int(input(u"输入被除数: ")) b = int(input(u"输入除数:")) div = a // b mod = a % b print("{} / {} =

  • JS求解两数之和算法详解

    本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法 利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num

  • 详解C语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0).根据通式写出算法不难,这里就不给出了.这里给出<编程之美>上的算法,主要是为了减少迭代的次数.      对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1).另外,如果x = p * x1,假设p为素数

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

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

  • 使用python实现两数之和的画解算法

    使用python实现两数之和的画解算法

    题目描述 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标. 你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现. 你可以按任意顺序返回答案. 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] . 示例 2: 输入:nums = [3,2,4],

  • python批量检查两个对应的txt文件的行数是否一致的实例代码

    在做深度学习的目标检测中,我们在测试好数据集后,可以用批量检查两个数据文件下面的标签文件,看看他们的行数是否一致,这样可以判断是否有漏检的情况,就不用一张张图片去看了. 对比两个标签文件的行数,可以发现有没有漏检.(对比的是打标的和训练后的标签) 代码如下: #coding=utf-8 import os, glob import numpy as np path1 = 'temp//1//' path2 = 'temp//2//' file_one_list = glob.glob(path1

  • 解决Python中回文数和质数的问题

    一.前言 今天学习视频时课后作业是找出1000以内既是素数又是回文数的数,写代码这个很容易,结果一运行遇到了bug,输出结果跟预期不一样,调试了快30min,再接着一通搜索和回看视频才发现问题所在.所以特地写下来,方便以后查看.问题的关键是判断素数过程中for-else的用法上(具体看后面代码) 二.实现判断素数的功能 质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个因数的数).via--Wikiped

  • C#获取两个数的最大公约数和最小公倍数示例

    最大公约数:指两个或多个整数共有约束中最大的一个. 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个. 复制代码 代码如下: /// <summary>/// 最大公约数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// &

随机推荐