פייתון/פייתון גרסה 3/אלגוריתם אוקלידס

אלגוריתם אוקלידס הוא שיטה למציאת מחלק משותף מקסימלי של שני איברים. לדוגמה המחלק המקסימלי המשותף של $36,24$ הוא $12$.

האלגוריתם

1. בהינתן שני מספרים, לדוגמה $42,36$, נבחר את המספר הגדול בניהם. במקרה שלנו נקח $42$.
2. נחלק את המספר הגדול במספר הקטן $42/36$.
3. נסמן ב-$r$ את השארית וב-$q$ את הגורם השני ($36$) שייצג בהמשך את המחלק המשותף. במקרה שלנו נקבל $42=1*36+6$ כאשר $r=6,q=36$
4. על פי האלגוריתם $gcd(a,b)=gcd(b,r)$ לכן נוכל לבצע שוב את החלוקה כלומר נבצע $gdc(36,6)$
5. נקבל $36=6*6+0$ כלומר $q=6$ וזהו המחלק הקטן ביותר.

קידוד

ישנם דרכים מגוונות לאלגוריתם. יש מי שמבצע החסרה ויש מי שמבצע חילוק:

def GCD(x,y): 
    while y > 0: 
        x,y = y,x%y 
    return x