Introduction

Lektion 10 von 20 im Kurs Mathematische Rätsel von Coddy.

Der größte gemeinsame Teiler (GCD) von zwei positiven Ganzzahlen x und y ist der größte Teiler, den x und y gemeinsam haben.

Zum Beispiel,

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

Der größte gemeinsame Teiler kann auch für drei oder mehr positive Ganzzahlen als der größte Teiler definiert werden, den alle gemeinsam haben. Zwei oder mehr positive Ganzzahlen, deren größter gemeinsamer Teiler 1 ist, werden als teilerfremd bezeichnet. [Weisstein, Eric W. "Greatest Common Divisor." Von MathWorld--Eine Wolfram Web-Ressource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Euklidischer Algorithmus zur Bestimmung des GCD

Die von Euklid eingeführte Methode zur Berechnung des größten gemeinsamen Teilers basiert auf der Tatsache, dass für zwei positive Ganzzahlen x und y mit y > x die gemeinsamen Teiler von x und y dieselben sind wie die gemeinsamen Teiler von y - x und x.

So besteht Euklids Methode zur Berechnung des größten gemeinsamen Teilers zweier positiver Ganzzahlen darin, die größere Zahl durch die Differenz der Zahlen zu ersetzen und dies zu wiederholen, bis die beiden Zahlen gleich sind: Das ist ihr größter gemeinsamer Teiler.

Beispiel: 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

Aufgabe

Einfach

Schreiben Sie Python-Code, gcd, der einen Vektor aus zwei Ganzzahlen, v, erhält und den größten gemeinsamen Teiler (GCD) für diese beiden gegebenen Zahlen findet.

Bitte beachten Sie, dass v[0] <= v[1] gilt.

Probier es selbst

#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;
}