pgcd.py

""" pgcd.py
"""
#! /usr/bin/python3
# -*- coding: utf-8 -*-

# PGCD = Plus Grand Commun Diviseur
# pgcd(a, b) = plus grand diviseur commun à a et b
# principe : a = b q + r
# les diviseurs communs à a et b divisent aussi r
# on remplace a par r et on recommence . . .
# voir aussi : bezout.py

import sys
import math

def pgcd(a, b):
    # plus grand diviseur commun à a et b
    # remarque : si a < b, à la première itération a et b sont échangés
    if type(a) != int :
        print("erreur type a")
        sys.exit(1) 
    # a  = b  q0 + r0
    # b  = r0 q1 + r1
    # r0 = r1 q2 + r2
    # r1 = r2 q3 + r3
    # quand rn = 0 donc pgcd = r(n-1)

    # for i in range (10):
    r = b
    while r != 0 :
        # % = modulo = reste de la divistion de a par b
        r = a % b
        # print(r)
        # bascule : (b, r) -> (a, b) pour l'itération suivante
        a = b
        b = r
    return a

x = pgcd (144, 89)
print("pgcd(144, 89) =", x)

x = pgcd (2*3*5*7*17, 2*3*11*13*19)
print("pgcd(2*3*5*7*17, 2*3*11*13*19) =", x)
"""
"""