Algoritmo euclideo

Lezione 11 di 20 del corso Indovinelli matematici di Coddy.

Un metodo più efficiente è l’algoritmo euclideo, una variante in cui la differenza tra i due numeri x e y viene sostituita dal resto della divisione di y per x.

Indicando questo resto come y mod x, l’algoritmo sostituisce ripetutamente (x, y) con (x, y mod x) finché la coppia non è (0, d), dove d è il massimo comune divisore.

Sfida

Medio

Scrivi il codice Python gcd2 che calcola il MCD, basandosi sull’algoritmo euclideo, e riceve un vettore v con due numeri dati.

Quanto è più veloce questo codice rispetto all’algoritmo di Euclide?

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 = gcd2(v, vn);
    printf("%d\n", r);
    return 0;
}