Python et quête n°3 - PGCD et algorithme d'Euclide

Vidéo montrant comment utiliser l'algorithme d'Euclide afin de déterminer le plus grand commun diviseur.

Script fonctionnant sous Python

# PGCD
#saisie des 2 nbres
a=int(input("Saisir le premier nombre entier: "))
b=int(input("Saisir le second nombre entier: "))


# classement et definition de gnbre et pnbre
if a<b:
    gnbre=b
    pnbre=a

else:
    gnbre=a
    pnbre=b

# declaration des listes pour garder une trace
dividende=[]
diviseur=[]
quotient=[]
reste=[]


# initialisation
i=0
r=1
dividende.append(gnbre)
diviseur.append(pnbre)


# boucle

while r!=0:
    q=dividende[i]//diviseur[i]
    r=dividende[i]%diviseur[i]
 
    quotient.append(q)
    reste.append(r)

    dividende.append(diviseur[i])
    diviseur.append(r)
    i=i+1


# Affichage
print("Le PGCD entre ",a," et ",b, "est donc ",dividende[-1])


# Pour  vérif, affichage des diviseurs de a et de b
i=2
aini=a
diviseura=[1]

while i<=a:
    if a%i ==0:
        diviseura.append(i)
        a=a/i

    else:
        i=i+1

print("Les diviseurs de ",aini," sont ",diviseura)


i=2
bini=b
diviseurb=[1]

while i<=b:
    if b%i ==0:
        diviseurb.append(i)
        b=b/i

    else:
        i=i+1

print("Les diviseurs de ",bini," sont ",diviseurb)

Test

>>> %Run PGCD.py

Saisir le premier nombre entier: 123405

Saisir le second nombre entier: 12045

Le PGCD entre  123405  et  12045 est donc  15

Les diviseurs de  123405  sont  [1, 3, 5, 19, 433]

Les diviseurs de  12045  sont  [1, 3, 5, 11, 73]