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

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

האלגוריתם עריכה

  1. בהינתן שני מספרים, לדוגמה  , נבחר את המספר הגדול בניהם. במקרה שלנו נקח  .
  2. נחלק את המספר הגדול במספר הקטן  .
  3. נסמן ב-  את השארית וב-  את הגורם השני ( ) שייצג בהמשך את המחלק המשותף. במקרה שלנו נקבל   כאשר  
  4. על פי האלגוריתם   לכן נוכל לבצע שוב את החלוקה כלומר נבצע  
  5. נקבל   כלומר   וזהו המחלק הקטן ביותר.

קידוד עריכה

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

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