Python 最大公约数算法

以下代码用于实现最大公约数算法：

实例(Python 3.0+)

# Filename : test.py # author by : www.runoob.com # 定义一个函数 def hcf(x, y): """该函数返回两个数的最大公约数""" # 获取最小值 if x > y: smaller = y else: smaller = x for i in range(1,smaller + 1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf # 用户输入两个数字 num1 = int(input("输入第一个数字: ")) num2 = int(input("输入第二个数字: ")) print( num1,"和", num2,"的最大公约数为", hcf(num1, num2))

执行以上代码输出结果为：

输入第一个数字: 54
输入第二个数字: 24
54 和 24 的最大公约数为 6

Document 对象参考手册 Python3 实例

Python ASCII码与字符相互转换

Python 最小公倍数算法

14 篇笔记写笔记

可按以下思路减少循环次数：

1. 当最小值为最大公约数时，直接返回；

2. 当最小值不为最大公约数时，最大公约数不会大于最小值的1/2；

3. 求最大公约数理应从大到小循环递减求最大。

实例：

def gcd(a, b):
    if b > a:
        a, b = b, a   # b为最小值
    if a % b == 0:
        return b      # 判断b是否为最大公约数
    for i in range(b//2+1, 1, -1):    # 倒序求最大公约数更合理
        if b % i == 0 and a % i == 0:
            return i
    return 0

while(True):
    a = int(input("Input 'a':"))
    b = int(input("Input 'b':"))
    print(gcd(a, b))

HaydnLiao7年前 (2017-07-02)

参考方法：

def gcd(x, y): # very fast
   return x if y == 0 else gcd(y, x%y)

print(gcd(378, 5940))  # result: 54

Joshua7年前 (2017-07-19)

参考方法：

x = int(input('请输入第一个数:'))
y = int(input('请输入第二个数:'))
for i in range(1,min(x,y) + 1):
    if (y % i == 0) & (x % i == 0):
        divisor = i
print(divisor)

thinrock7年前 (2017-08-17)

从大到小一个一个计算：

n1=int(input("input a number: "))
n2=int(input("input another number: "))
if n1<n2:
    smaller=n1
else:
    smaller=n2
while True:
    if (n1%smaller==0) and (n2%smaller==0):
        print(smaller)
        break
    smaller-=1

Santana7年前 (2017-09-09)

#0
susion
245***1461@qq.com
14
两个数的最大公约数可以使用欧几里得算法实现。即两个数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
```
def gcd(a, b):
  if a == 0:
    a, b = b, a
  while b != 0:
    a, b = b, a % b
  return a

print(gcd(54, 24))
```
susion
susion
245***1461@qq.com
7年前 (2017-10-15)

可以利用辗转相除的方法实现求两个正数的最大公约数，代码如下：

#!/usr/bin/python3
# -*- coding: UTF-8 -*-

# find the greatest common divisor of two integer

def find_GCD(x, y):
  find_GCD = y
  while (x % y) != 0:
    find_GCD = x % y
    x, y = y, find_GCD
  return find_GCD

int1 = int(input('Input 1st integer: '))
int2 = int(input('Input 2nd integer: '))

print('The greatest common divisor of {} and {} is {}'.format(int1, int2, find_GCD(int1, int2)))

代码运行结果如下：

Input 1st integer: 54
Input 2nd integer: 24
The greatest common divisor of 54 and 24 is 6

黄桃果捞6年前 (2018-03-20)

欧几得里算法的完善版，输入任意两个整数，求最大公约数。

def gcd(a,b):
    if a == 0:
        a,b = b,a
    while b != 0:
        a,b = b,a%b
    return a

c = int(input('请输入第一个正整数: '))
d = int(input('请输入第二个正整数: '))

if c>d:
   b = d
else:
   b = c

print('{}和{}的最大公约数为: {}'.format(c,d,gcd(c,d)))

桃之夭夭6年前 (2018-06-28)

不能再精简了吧

# 辗转相除法(不用判断大小)
def f1(a,b):
    while b!=0:
        a,b=b,a%b
    print(a)
f1(27,6)

# 相减法
def f2(a,b):
    while a!=b:
        a,b=min(a,b),abs(a-b)
    print(a)
f2(27,6)

Egg_Hu6年前 (2018-07-24)

求多个数的最大公约数

num = str(input('输入要检测的数字(如：5,25,75)：')).split(',')
ss,kk,ee= [],[],[]
for i in num:
    ss.append(int(i))   #将输入的数字存入列表
for j in ss:
    for m in range(1,1+max(ss)):
        if(j % m ==0):
            kk.append(m)    #求出输入的每一个数字的约数，并将其存入列表
for q in kk:
    if(kk.count(q)==len(ss)):
            ee.append(q)      #将所有的公约数存入列表
print(ee)
print('{}的最大公约数为：{}'.format(ss,max(ee)))  #输出最大公约数

测试结果：

输入要检测的数字：5,25,75
[1, 5, 1, 5, 1, 5]
[5, 25, 75]的最大公约数为：5

The_Matrix6年前 (2018-08-01)

#0
Alex
934***001@qq.com
20
使用 math 模块的 gcd()。
```
import math

a = 54
b = 24
print(math.gcd(a, b))
```
输出结果为：
```
6
```
Alex
Alex
934***001@qq.com
6年前 (2018-11-12)

参考方法：

# 没办法，就喜欢用 filter，能用 filter 解决的，坚决不用循环，哇哈哈哈

while True:
    try:
        n1=int(input('请输入第 1 个数字:'))
        n2=int(input('请输入第 2 个数字:'))
        L1=list(filter(lambda x:n1%x==0,range(1,n1)))
        L2=list(filter(lambda x:n2%x==0,range(1,n2)))
        L=list(filter(lambda x:x in L2,L1))
        print('{0}共有{1}个公约数，分别为{2}，最大公约数为{3}'.format((n1,n2),len(L),L,max(L)))
        break
    except ValueError:
        print('输入正整数')

慕容君少5年前 (2018-11-22)

用空列表方式实现最大公约数：

'''最大公约数'''
def hcf(x,y):
    list = []    #初始化一个空列表
    for i in range(1,min(x,y)+1):
        if (x % i == 0) & (y % i == 0):
            list.append(i)  #将符合的值加到列表中
    print(max(list))     #求列表中最大值，有内置函数
hcf(18,12)

favourite455年前 (2019-07-14)

求两个数的所有公约数:

list = []

def hec(x, y):
    value = max(x, y)
    for i in range(1, value+1):
        if((x % i == 0) and (y % i == 0)):
            list.append(i)

num1 = int(input("Please input the first number:"))
num2 = int(input("Please input the secend number:"))
hec(num1, num2)
print(num1, "and", num2, "of Maximum common divisor is：",list)

白云黑土5年前 (2019-10-26)

这个时间复杂度太高了吧，好像有一个叫辗转相除法的，效率很高:

def func2():
    num1 = int(input("请输入第一个数字："))
    num2 = int(input("请输入第一个数字："))
    m = max(num1, num2)
    n = min(num1, num2)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    print(num1, "和", num2, "的最大公约数为", n)
    
if __name__ == '__main__':
    func2()

残存的影子1年前 (2023-02-25)

菜鸟教程 -- 学的不仅是技术，更是梦想！

Python3 高级教程

Python 最大公约数算法

实例(Python 3.0+)

14 篇笔记写笔记

点我分享笔记

菜鸟教程 -- 学的不仅是技术，更是梦想！

Python3 高级教程

Python 最大公约数算法

实例(Python 3.0+)

14 篇笔记 写笔记

点我分享笔记

微信关注

14 篇笔记写笔记