Introduzione

Lezione 10 di 20 del corso Indovinelli matematici di Coddy.

Il massimo comune divisore (GCD) di due numeri interi positivi x e y è il più grande divisore comune a x e y.

Per esempio,

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

Il massimo comune divisore può essere definito anche per tre o più numeri interi positivi come il più grande divisore condiviso da tutti. Due o più numeri interi positivi che hanno massimo comune divisore 1 si dicono coprimi tra loro. [Weisstein, Eric W. "Greatest Common Divisor." Da MathWorld--Una risorsa web Wolfram. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Algoritmo di Euclide per trovare il GCD

Il metodo introdotto da Euclide per calcolare i massimi comuni divisori si basa sul fatto che, dati due numeri interi positivi x e y tali che y > x, i divisori comuni di x e y sono gli stessi dei divisori comuni di y - x e x.

Quindi, il metodo di Euclide per calcolare il massimo comune divisore di due numeri interi positivi consiste nel sostituire il numero più grande con la differenza tra i numeri e ripetere questa operazione finché i due numeri non sono uguali: quello è il loro massimo comune divisore.

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

Sfida

Facile

Scrivi il codice Python, gcd, che riceve un vettore di due numeri interi, v, e trova il GCD di quei due numeri.

Tieni presente che v[0] <= v[1].

Provalo tu

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