מבוא

שיעור 10 מתוך 20 בקורס חידות מתמטיות של Coddy.

המחלק המשותף הגדול ביותר של שני מספרים שלמים חיוביים x ו-y הוא המחלק הגדול ביותר המשותף ל-x ול-y (GCD).

לדוגמה,

GCD(6, 15) = 3
GCD(7, 13) = 1
GCD(18, 30) = 6

אפשר להגדיר מחלק משותף גדול ביותר גם עבור שלושה או יותר מספרים שלמים חיוביים, כמחלק הגדול ביותר המשותף לכולם. שני מספרים שלמים חיוביים או יותר שהמחלק המשותף הגדול ביותר שלהם הוא 1 נקראים זרים זה לזה. [Weisstein, Eric W. "Greatest Common Divisor." מתוך MathWorld--משאב אינטרנט של Wolfram. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

האלגוריתם של אוקלידס למציאת GCD

השיטה שהציג אוקלידס לחישוב המחלקים המשותפים הגדולים ביותר מבוססת על העובדה שבהינתן שני מספרים שלמים חיוביים x ו-y כך ש-y > x, המחלקים המשותפים של x ושל y זהים למחלקים המשותפים של y - x ושל x.

לכן, השיטה של אוקלידס לחישוב המחלק המשותף הגדול ביותר של שני מספרים שלמים חיוביים מורכבת מהחלפת המספר הגדול יותר בהפרש בין המספרים, וחזרה על כך עד ששני המספרים שווים: זהו המחלק המשותף הגדול ביותר שלהם.

דוגמה: GCD(6, 15) = GCD(6, 15 - 6) = GCD(6, 9) = GCD(6, 9 - 6) = GCD(6, 3) = GCD(6 - 3, 3) = GCD(3, 3) = 3

אתגר

קל

כתבו קוד Python, gcd, שמקבל וקטור של שני מספרים שלמים, v, ומוצא את ה-GCD של שני המספרים הנתונים.

שימו לב ש-v[0] <= v[1].

נסו בעצמכם

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int v[4096];
    int vn = 0;
    char line[65536];
    if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
    char* tok = strtok(line, " \t\r\n");
    while (tok) { v[vn++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int r = gcd(v, vn);
    printf("%d\n", r);
    return 0;
}