Code pour le plus grand diviseur commun en Python [fermé]

108

Le plus grand diviseur commun (GCD) de a et b est le plus grand nombre qui les divise tous les deux sans reste.

Une façon de trouver le GCD de deux nombres est l'algorithme d'Euclid, qui est basé sur l'observation que si rest le reste quand aest divisé par b, alors gcd(a, b) = gcd(b, r). Comme cas de base, nous pouvons utiliser gcd(a, 0) = a.

Ecrivez une fonction appelée gcd qui prend les paramètres aet bet renvoie leur plus grand diviseur commun.

Luc D
la source

Réponses:

300

C'est dans la bibliothèque standard .

>>> from fractions import gcd
>>> gcd(20,8)
4

Code source du inspectmodule en Python 2.7:

>>> print inspect.getsource(gcd)
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

À partir de Python 3.5, se gcd trouve dans le mathmodule ; celui de fractionsest obsolète. De plus, inspect.getsourcene renvoie plus le code source explicatif pour l'une ou l'autre méthode.

user545424
la source
3
Il ne renvoie pas "le plus grand nombre_ qui les divise tous les deux sans reste" par exemple, fractions.gcd(1, -1)est -1mais 1 > -1c'est-à-dire 1divise les deux 1et -1sans reste et il est plus grand que -1, voir bugs.python.org/issue22477
jfs
1
@JFSebastian Je ne vois pas cela comme un problème ... il suffit de regarder le commentaire dans le code source: "Sauf si b == 0, le résultat aura le même signe que b" , donc gcd(1, -1) == -1me semble totalement légitime.
Marco Bonelli
@MarcoBonelli: oui. Il se comporte comme documenté mais ce n'est pas la définition du manuel que la plupart des gens connaissent. Lisez la discussion que j'ai liée ci-dessus . Personnellement, j'aime tel fractions.gcd()quel (il fonctionne sur les éléments d'anneau euclidien).
jfs
1
@JFSebastian FWIW, à partir de Python 3.5, math.gcd(1, -1)retourne 1.
Acumenus
1
@ABB math.gcd () et fractions.gcd () sont différents comme indiqué dans la réponse et les commentaires.
jfs
39

Les algorithmes avec mn peuvent être extrêmement longs.

Celui-ci fonctionne beaucoup mieux:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x
netom
la source
5
C'est également celui de la bibliothèque standard.
sayantankhan
10
Comment fonctionne cet algorithme? c'est comme de la magie.
dooderson
20
@netom: non, l'affectation ne peut pas être écrite comme ça; l'affectation de tuple utilise xavant d'être affectée. Vous avez attribué yà la x première , donc maintenant yva être défini sur 0(comme y % ytoujours 0).
Martijn Pieters
1
@MartijnPieters oui, vous avez raison, j'aurais dû utiliser une variable temporaire. comme ceci: x_ = y; y = x% y; x = x_
netom
3
@netom: ce qui n'est pas du tout nécessaire lors de l'utilisation d'une affectation de tuple comme dans cette réponse.
Martijn Pieters
18

Cette version de code utilise l'algorithme d'Euclid pour trouver GCD.

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)
Ankush
la source
28
Vous avez utilisé iter dans le nom mais c'est en fait une version récursive.
Shiplu Mokaddim le
la récursivité est peu efficace par rapport aux versions en boucle, + vous devez l'appeler avec b> a
Dr. Goulu
1
def gcd(a, b): if b == 0: return a return gcd(b, a % b)
Andreas K.
16
gcd = lambda m,n: m if not n else gcd(n,m%n)
Jonas Byström
la source
3
def gcd(m,n):
    return gcd(abs(m-n), min(m, n)) if (m-n) else n
dansalmo
la source
5
N'utilisez jamais «est» lorsque vous voulez comparer l'égalité. Le cache des petits entiers est un détail d'implémentation CPython.
Marius Gedminas
2

Solution très concise utilisant la récursivité:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
Preetika Mondal
la source
2

en utilisant la récursivité ,

def gcd(a,b):
    return a if not b else gcd(b, a%b)

en utilisant while ,

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

en utilisant lambda,

gcd = lambda a,b : a if not b else gcd(b, a%b)

>>> gcd(10,20)
>>> 10
Mohideen bin Mohammed
la source
1
La version lambda ne peut pas fonctionner car elle n'a aucune condition pour arrêter la récursivité. Je pense que cela appelle simplement votre fonction précédemment définie.
rem
1
a=int(raw_input('1st no \n'))
b=int(raw_input('2nd no \n'))

def gcd(m,n):
    z=abs(m-n)
    if (m-n)==0:
        return n
    else:
        return gcd(z,min(m,n))


print gcd(a,b)

Une approche différente basée sur l'algorithme d'euclid.


la source
1
def gcdRecur(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    # Base case is when b = 0
    if b == 0:
        return a

    # Recursive case
    return gcdRecur(b, a % b)
SHAMS
la source
1

Je pense qu'une autre façon est d'utiliser la récursivité. Voici mon code:

def gcd(a, b):
    if a > b:
        c = a - b
        gcd(b, c)
    elif a < b:
        c = b - a
        gcd(a, c)
    else:
        return a
dexhunter
la source
Vous ne gcd(10,5)
revenez
0

en python avec récursivité:

def gcd(a, b):
    if a%b == 0:
        return b
    return gcd(b, a%b)
Keajer
la source
0
def gcd(a,b):
    if b > a:
        return gcd(b,a)
    r = a%b
    if r == 0:
        return b
    return gcd(r,b)
dpeleg2000
la source
0

Pour a>b:

def gcd(a, b):

    if(a<b):
        a,b=b,a
        
    while(b!=0):
        r,b=b,a%r
        a=r
    return a

Pour l'un a>bou l' autre ou a<b:

def gcd(a, b):

    t = min(a, b)

    # Keep looping until t divides both a & b evenly
    while a % t != 0 or b % t != 0:
        t -= 1

    return t
Rao Baswaraj
la source
4
échange vars en python est les enfants jouer: b, a = a, b. essayez d'en savoir plus sur la langue
Jason Hu
3
J'aime ce que vous dites, mais je n'aime pas la façon dont vous le dites
JackyZhu
0

J'ai dû faire quelque chose comme ça pour un devoir à la maison en utilisant des boucles while. Ce n'est pas le moyen le plus efficace, mais si vous ne souhaitez pas utiliser une fonction, cela fonctionne:

num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
    if num1 % x == 0:
        num1_list.append(x)
    x += 1
while y <= num2:
    if num2 % y == 0:
        num2_list.append(y)
    y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])
Vanessa
la source
0
def _grateest_common_devisor_euclid(p, q):
    if q==0 :
        return p
    else:
        reminder = p%q
        return _grateest_common_devisor_euclid(q, reminder)

print(_grateest_common_devisor_euclid(8,3))
Sai Prateek
la source
-1

Ce code calcule le pgcd de plus de deux nombres en fonction du choix donné par # l'utilisateur, ici l'utilisateur donne le nombre

numbers = [];
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?\n")
for i in range(0, count):
  number = input("ENTER THE NUMBER : \n")
  numbers.append(number)
numbers_sorted = sorted(numbers)
print  'NUMBERS SORTED IN INCREASING ORDER\n',numbers_sorted
gcd = numbers_sorted[0]

for i in range(1, count):
  divisor = gcd
  dividend = numbers_sorted[i]
  remainder = dividend % divisor
  if remainder == 0 :
  gcd = divisor
  else :
    while not remainder == 0 :
      dividend_one = divisor
      divisor_one = remainder
      remainder = dividend_one % divisor_one
      gcd = divisor_one

print 'GCD OF ' ,count,'NUMBERS IS \n', gcd
Prashant
la source
5
Bienvenue dans Stack Overflow! Envisageriez-vous d'ajouter un récit pour expliquer pourquoi ce code fonctionne et ce qui en fait une réponse à la question? Cela serait très utile à la personne qui pose la question et à toute autre personne qui se présente.
Andrew Barber
-1

L'échange de valeur n'a pas bien fonctionné pour moi. Je viens donc de mettre en place une situation de type miroir pour les nombres entrés dans a <b OU a> b:

def gcd(a, b):
    if a > b:
        r = a % b
        if r == 0:
            return b
        else:
            return gcd(b, r)
    if a < b:
        r = b % a
        if r == 0:
            return a
        else:
            return gcd(a, r)

print gcd(18, 2)
Troïchroi
la source
2
Ce n'est même pas une syntaxe Python valide. L'indentation est importante.
Marius Gedminas
2
Et quand a = b? vous devriez avoir une condition IF initiale pour attraper cela.
josh.thomson
-2
#This program will find the hcf of a given list of numbers.

A = [65, 20, 100, 85, 125]     #creates and initializes the list of numbers

def greatest_common_divisor(_A):
  iterator = 1
  factor = 1
  a_length = len(_A)
  smallest = 99999

#get the smallest number
for number in _A: #iterate through array
  if number < smallest: #if current not the smallest number
    smallest = number #set to highest

while iterator <= smallest: #iterate from 1 ... smallest number
for index in range(0, a_length): #loop through array
  if _A[index] % iterator != 0: #if the element is not equally divisible by 0
    break #stop and go to next element
  if index == (a_length - 1): #if we reach the last element of array
    factor = iterator #it means that all of them are divisibe by 0
iterator += 1 #let's increment to check if array divisible by next iterator
#print the factor
print factor

print "The highest common factor of: ",
for element in A:
  print element,
print " is: ",

plus grand_common_devisor (A)

user4713071
la source
-2
def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
    if (a%gcd==0 and b%gcd==0):
        return gcd
        break
    gcd-=1
Par bas
la source
C'est le moyen le plus simple ... Ne compliquez pas les choses!
Par bas
3
Merci d'avoir fourni du code qui pourrait aider à résoudre le problème, mais en général, les réponses sont beaucoup plus utiles si elles incluent une explication de ce que le code est censé faire et pourquoi cela résout le problème.
Neuron
1
Ce code est incomplet (pas de déclaration de retour finale) et mal formaté (pas d'indentation). Je ne suis même pas sûr de ce que cette breakdéclaration tente de réaliser.
kdopen
-2

Voici la solution mettant en œuvre le concept de Iteration:

def gcdIter(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    if a > b:
        result = b
    result = a

    if result == 1:
        return 1

    while result > 0:
        if a % result == 0 and b % result == 0:
            return result
        result -= 1
Bikramjeet Singh
la source