最大公约数（GCD）

Question

def get_divs(z):
      return [i for i in range(1, z) if z % i == 0]

def gcd(x, y):
      x_div=get_divs(x)
      y_div=get_divs(y)
      cd=set(x_div).intersection(y_div)
      gcd=cd[-1]
      print("The GCD of",x,"and",y,"is",gcd)
      return 1

我试图让这个程序计算两个用户输入的正整数（x和y）的最大公约数（GCD）。set函数不返回可以索引的列表。关于如何找到GCD有什么建议吗？

Answer 1

抱歉5年后回复。但是你可以用欧几里德算法找到GCD。下面是代码：

a = int(input('Enter 1st number: '))
b = int(input('Enter 2nd number: '))
r = a%b
while (r!=0):
    a=b
    b=r
    r = a%b
print(f'greatest common divisor is {b}')

Answer 2

下面是算法应该是什么样子。

findGCD(int firstNum, int secondNum){
int smaller; int bigger;int remainder;
if(firstNum < secondNum) {
    smaller = firstNum;
    bigger = secondNum;
}  
else {
    smaller =  secondNum;
    bigger = firstNum;
}

while(true) {
    remainder = bigger % smaller;
    if(remainder == 0) {
         break;
    }
    else {
         bigger = smaller;
         smaller = remainder;
    }
}
return smaller;
}