Euclidean algorithm

Lección 11 de 20 del curso Acertijos matemáticos de Coddy.

Un método más eficiente es el algoritmo de Euclides, una variante en la que la diferencia de los dos números x e y se sustituye por el resto de la división de y entre x.

Denotando este resto como y mod x, el algoritmo reemplaza (x, y) por (x, y mod x) repetidamente hasta que el par es (0, d), donde d es el máximo común divisor.

Desafío

Intermedio

Escribe código python, gcd2, que calcule el MCD, basado en el algoritmo de Euclides, que reciba un vector v con dos números dados.

¿Qué tan rápido es este código comparado con el algoritmo de Euclides?

Pruébalo tú mismo

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