Greatest Common Divisor

Q: Quelle est la complexité temporelle de l’algorithme d’Euclide ?

Il s’exécute en O(log(min(a, b))) étapes, car toutes les deux étapes, le plus grand nombre est au moins divisé par deux. Le pire des cas correspond à une paire de nombres de Fibonacci consécutifs. Pour des nombres allant jusqu’à 10^9 , cela représente au plus 43 étapes, et l’algorithme utilise un espace supplémentaire de O(1) .

Q: Pourquoi gcd(a, b) est-il égal à gcd(b, a % b) ?

Écrivez a = q × b + r avec r = a % b . Un nombre qui divise a et b divise a - q × b , qui est r . Un nombre qui divise b et r divise q × b + r , qui est a . Les deux paires ont les mêmes diviseurs communs, elles ont donc le même plus grand diviseur.

DébutantMaths et simulation

+10

Vous recevez deux entiers positifs a et b. Retournez leur plus grand commun diviseur : le plus grand entier qui divise les deux sans reste.

Par exemple, les nombres qui divisent à la fois 8 et 12 sont 1, 2 et 4, donc la réponse est 4.

Fonction

gcd(a: integer, b: integer) → integer

ainteger: le premier entier positif
binteger: le deuxième entier positif
Renvoieinteger: le plus grand entier qui divise à la fois a et b

Contraintes

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Exemples

Entrée: a = 12b = 18
Sortie: 6
Explication: Les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12 ; les diviseurs de 18 sont 1, 2, 3, 6, 9 et 18. Le plus grand des deux est 6.

Entrée: a = 17b = 5
Sortie: 1
Explication: 17 et 5 sont tous deux premiers et différents, donc le seul diviseur qu’ils ont en commun est 1.

Entrée: a = 42b = 42
Sortie: 42
Explication: Un nombre est divisible par lui-même, et aucun nombre supérieur à 42 ne peut diviser 42, donc le plus grand commun diviseur de 42 et 42 est 42.

+14 tests cachés à la soumission

Pour aller plus loin

Peux-tu étendre l’algorithme d’Euclide pour qu’il renvoie aussi des entiers x et y tels que a × x + b × y = gcd(a, b) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La définition suggère d’essayer les candidats un par un, ce qui fonctionne avec de petits nombres. Cependant, avec a et b pouvant atteindre 10^9, deux grands nombres qui n’ont aucun facteur commun obligent à faire un milliard d’essais. L’observation d’Euclide selon laquelle gcd(a, b) est égal à gcd(b, a % b) réduit les nombres si rapidement qu’aucune paire jusqu’à 10^9 ne nécessite plus de 43 étapes.

Comptez à rebours à partir du plus petit nombre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Aucun diviseur commun ne peut être supérieur au plus petit des deux nombres, car un diviseur de b est au plus égal à b. Commence donc avec un candidat d égal à min(a, b) et diminue-le de un jusqu’à ce qu’il divise les deux nombres. Comme tu essaies les candidats en partant du plus grand, le premier qui convient est le plus grand.

Pour 12 et 18, tu essaies 12 (il ne divise pas 18), puis 11, 10, 9, 8 et 7, qui ne conviennent pas, et tu t’arrêtes à 6. La boucle se termine toujours, car 1 divise tous les nombres.

Le coût correspond au nombre de candidats. Pour 999999937 et 999999929, deux nombres premiers, la réponse est 1 et la boucle s’exécute presque 10^9 fois. C’est beaucoup trop lent pour les tests les plus volumineux.

Algorithme

Définis d comme étant le plus petit de a et b.
Tant que a % d ou b % d n’est pas égal à 0, soustrais 1 à d.
Renvoie d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Algorithme d’Euclide

Intuition

Écrivez a = q × b + r, où r = a % b. Tout nombre qui divise à la fois a et b divise aussi r = a - q × b. Tout nombre qui divise à la fois b et r divise aussi a = q × b + r. Ainsi, les paires (a, b) et (b, r) ont exactement les mêmes diviseurs communs, et le même plus grand diviseur commun.

Remplacez (a, b) par (b, a % b) et répétez jusqu’à ce que b devienne 0. Tout nombre divise 0, donc gcd(a, 0) = a et a est la réponse. Pour 12 et 18 : (12, 18) devient (18, 12), puis (12, 6), puis (6, 0), et la réponse est 6. La première étape inverse les nombres à elle seule lorsque a est plus petit ; vous n’avez donc jamais besoin de les trier.

Tous les deux pas, le plus grand nombre est au moins divisé par deux ; la boucle s’exécute donc O(log(min(a, b))) fois. Les entrées les plus lentes sont des nombres de Fibonacci consécutifs, comme 701408733 et 433494437, et même celles-ci ne nécessitent que 42 étapes.

Algorithme

Tant que b n’est pas 0, calculez r = a % b.
Définissez a = b et b = r.
Lorsque b atteint 0, renvoyez a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Pièges et cas limites

L’algorithme est court : les bogues viennent donc de la mise à jour et de la condition d’arrêt.

Mettre à jour dans le mauvais ordre. a = b suivi de b = a % b calcule b % b, qui vaut toujours 0, et renvoie b. Enregistrez d’abord le reste dans une variable temporaire, ou effectuez les deux affectations en même temps.
Renvoyer b au lieu de a à la fin de la boucle. À ce moment-là, b vaut 0.
Arrêter le compte à rebours à 2 ou le commencer à max(a, b). Dans le premier cas, on rate des paires de nombres premiers entre eux, comme 17 et 5 ; dans le second, on perd du temps à tester des candidats qui ne peuvent pas diviser le plus petit nombre.
Utiliser des soustractions répétées au lieu du reste. gcd(10^9, 1) nécessite alors un milliard de soustractions ; % les effectue toutes en une seule étape.

Questions fréquentes4

Quelle est la complexité temporelle de l’algorithme d’Euclide ?

Il s’exécute en O(log(min(a, b))) étapes, car toutes les deux étapes, le plus grand nombre est au moins divisé par deux. Le pire des cas correspond à une paire de nombres de Fibonacci consécutifs. Pour des nombres allant jusqu’à 10^9, cela représente au plus 43 étapes, et l’algorithme utilise un espace supplémentaire de O(1).

Pourquoi gcd(a, b) est-il égal à gcd(b, a % b) ?

Écrivez a = q × b + r avec r = a % b. Un nombre qui divise a et b divise a - q × b, qui est r. Un nombre qui divise b et r divise q × b + r, qui est a. Les deux paires ont les mêmes diviseurs communs, elles ont donc le même plus grand diviseur.

Quelle est la différence entre le PGCD et le PPCM ?

Le plus grand commun diviseur est le plus grand nombre qui divise les deux entrées ; le plus petit commun multiple est le plus petit nombre divisible par les deux entrées. Ils sont liés par gcd(a, b) × lcm(a, b) = a × b, donc une fois le PGCD obtenu, le PPCM est a / gcd(a, b) × b.

Quel est le PGCD de deux nombres premiers entre eux ?

Deux nombres sont premiers entre eux lorsque leur plus grand diviseur commun est 1, ce qui signifie qu’ils ne partagent aucun facteur premier. Deux nombres premiers différents sont toujours premiers entre eux, tout comme deux entiers consécutifs, tels que 8 et 9.

Python

def gcd(a, b):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

a = 12
b = 18

Attendu