求最大公约数

ZYM111

def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x
   
print(gcd(4, 6))
求这题有别的方法做？作者能不能发点刚入门的人一点一下能反应过来的代码？？？？？？？？？？？？？

新手·ing

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

gopythoner

不知道你说的能看懂是个什么概念，我就按照数学的逻辑来写一个很长，但是很通俗易懂的吧
但愿我没有把公约数的概念记错

def gcd(x,y):
    # 公约数不止一个，所以应该是个列表，先定义这个列表为the_nums
    the_nums = []
    # 得到x的所有约数,也是个列表，定义为x_nums
    x_nums = []
    # 把a当做x的约数，那a肯定满足如下条件，即2<=a<=x,表达方式如下
    for a in range(2,x+1):
        # 约数还有一个条件就是整除，表达成这样
        if x % a == 0:
            # 好了，通过上述2个条件就得到了所有满足条件的a，也就是x的所有约数，加入的列表中
            x_nums.append(a)
    # 同理，可以得到y的约数集合
    y_nums = []
    for b in range(2,y+1):
        if y % b == 0:
            y_nums.append(b)
    # 接下来就是公约数了，定义为t，它应该满足同时在x和y的约数集合中，表达如下
    for t in x_nums:
        if t in y_nums:
            # 把所有满足条件的t加入到最开始定义的列表中
            the_nums.append(t)
    return the_nums

# 测试一下：
print(gcd(6,4))
# >>>[2]
print(gcd(20,40))
# >>>[3]

gopythoner

gopythoner 发表于 2017-3-26 01:25
不知道你说的能看懂是个什么概念，我就按照数学的逻辑来写一个很长，但是很通俗易懂的吧
但愿我没有把公约 ...

gcd(20,40)的答案应该是这个，我复制错了
[2, 4, 5, 10, 20]

ZYM111

gopythoner 发表于 2017-3-26 01:25
不知道你说的能看懂是个什么概念，我就按照数学的逻辑来写一个很长，但是很通俗易懂的吧
但愿我没有把公约 ...

谢谢 很好懂

流月飞星

SuMo

那道课后习题的要求是让你根据那个啥公理的方式来求解.......
你把公理看懂了 ,也就知道大概的逻辑了
# def gcd(x,y):
#    if x == 0 or y ==0:
#        return max(x,y)
#    minx = x if x<y else y
#    return gcd(minx,x%y)   
#  
# print gcd(18,9)