Introduction

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

El máximo común divisor (MCD) de dos números enteros positivos x e y es el mayor divisor común a x e y.

Por ejemplo,

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

El máximo común divisor también puede definirse para tres o más números enteros positivos como el mayor divisor compartido por todos ellos. Se dice que dos o más números enteros positivos que tienen como máximo común divisor 1 son primos entre sí. [Weisstein, Eric W. "Greatest Common Divisor." De MathWorld--Un recurso web de Wolfram. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Algoritmo de Euclides para encontrar el MCD

El método introducido por Euclides para calcular los máximos comunes divisores se basa en el hecho de que, dados dos números enteros positivos x e y tales que y > x, los divisores comunes de x e y son los mismos que los divisores comunes de y - x y x.

Así, el método de Euclides para calcular el máximo común divisor de dos números enteros positivos consiste en reemplazar el número mayor por la diferencia de los números, y repetir esto hasta que los dos números sean iguales: ese es su máximo común divisor.

Ejemplo: MCD(6, 15) = MCD(6, 15 - 6) = MCD(6, 9) = MCD(6, 9 - 6) = MCD(6, 3) = MCD(6 - 3, 3) = MCD(3, 3) = 3

Desafío

Fácil

Escribe código python, gcd, que reciba un vector de dos enteros, v, y encuentre el MCD (Máximo Común Divisor) para esos dos números dados.

Ten en cuenta que v[0] <= v[1].

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