以下代码用于实现最大公约数算法:
执行以上代码输出结果为:
输入第一个数字: 54 输入第二个数字: 24 54 和 24 的最大公约数为 6
HaydnLiao
Hay***[email protected]
可按以下思路减少循环次数:
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))HaydnLiao
Hay***[email protected]
Joshua
cos***[email protected]
参考方法:
def gcd(x, y): # very fast return x if y == 0 else gcd(y, x%y) print(gcd(378, 5940)) # result: 54
Joshua
cos***[email protected]
thinrock
thi***[email protected]
参考方法:
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)thinrock
thi***[email protected]
Santana
378***[email protected]
从大到小一个一个计算:
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
Santana
378***[email protected]
susion
245***[email protected]
两个数的最大公约数可以使用 欧几里得算法实现。即两个数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
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
245***[email protected]
黄桃果捞
zhe***[email protected]
可以利用辗转相除的方法实现求两个正数的最大公约数,代码如下:
#!/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
黄桃果捞
zhe***[email protected]
桃之夭夭
956***[email protected]
欧几得里算法的完善版,输入任意两个整数,求最大公约数。
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)))桃之夭夭
956***[email protected]
Egg_Hu
799***[email protected]
不能再精简了吧
# 辗转相除法(不用判断大小) 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_Hu
799***[email protected]
The_Matrix
995***[email protected]
求多个数的最大公约数
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_Matrix
995***[email protected]
Alex
934***[email protected]
使用 math 模块的 gcd()。
import math a = 54 b = 24 print(math.gcd(a, b))
输出结果为:
6
Alex
934***[email protected]
慕容君少
shu***[email protected]
参考方法:
# 没办法,就喜欢用 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('输入正整数')慕容君少
shu***[email protected]
favourite45
jas***[email protected]
用空列表方式实现最大公约数:
'''最大公约数''' 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)
favourite45
jas***[email protected]
白云黑土
mr.***[email protected]
求两个数的所有公约数:
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)白云黑土
mr.***[email protected]
残存的影子
176***[email protected]
这个时间复杂度太高了吧,好像有一个叫辗转相除法的,效率很高:
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()残存的影子
176***[email protected]