Wprowadzenie

Lekcja 10 z 20 w kursie Zagadki matematyczne w Coddy.

Największy wspólny dzielnik (GCD) dwóch dodatnich liczb całkowitych x i y to największy dzielnik wspólny dla x i y.

Na przykład,

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

Największy wspólny dzielnik można również zdefiniować dla trzech lub więcej dodatnich liczb całkowitych jako największy dzielnik wspólny dla wszystkich tych liczb. O dwóch lub więcej dodatnich liczbach całkowitych, których największy wspólny dzielnik wynosi 1, mówi się, że są względnie pierwsze. [Weisstein, Eric W. „Greatest Common Divisor”. Z MathWorld — zasobu internetowego Wolframa. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Algorytm Euklidesa do znajdowania GCD

Metoda wprowadzona przez Euklidesa do obliczania największych wspólnych dzielników opiera się na fakcie, że dla dwóch dodatnich liczb całkowitych x i y, takich że y > x, wspólne dzielniki x i y są takie same jak wspólne dzielniki y - x i x.

Metoda Euklidesa do obliczania największego wspólnego dzielnika dwóch dodatnich liczb całkowitych polega więc na zastępowaniu większej liczby różnicą tych liczb i powtarzaniu tego działania, aż obie liczby będą równe: ich wspólny wynik jest ich największym wspólnym dzielnikiem.

Przykład: 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

Wyzwanie

Łatwy

Napisz kod w Pythonie, gcd, który otrzymuje wektor dwóch liczb całkowitych, v, i znajduje NWD tych dwóch podanych liczb.

Zwróć uwagę, że v[0] <= v[1].

Spróbuj swoich sił

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