PGCD (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 

Je suis en train d'obtenir ce programme pour calculer le PGCD (GCD) de deux entrées par l'utilisateur, des nombres entiers positifs (x et y). La fonction set ne retourne pas une liste pouvant être indexée. Des suggestions sur la façon dont je peux trouver le GCD?

Answer 1

Voici à quoi devrait ressembler l'algo.

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; 
}