Introduction

Lição 10 de 20 do curso Enigmas Matemáticos da Coddy.

O máximo divisor comum (MDC), de dois números inteiros positivos x e y, é o maior divisor comum a x e y.

Por exemplo,

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

O máximo divisor comum também pode ser definido para três ou mais números inteiros positivos como o maior divisor compartilhado por todos eles. Dois ou mais números inteiros positivos que têm o máximo divisor comum igual a 1 são ditos primos entre si. [Weisstein, Eric W. "Greatest Common Divisor." De MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Algoritmo de Euclides para encontrar o MDC

O método introduzido por Euclides para calcular os máximos divisores comuns baseia-se no fato de que, dados dois números inteiros positivos x e y tais que y > x, os divisores comuns de x e y são os mesmos que os divisores comuns de y - x e x.

Portanto, o método de Euclides para calcular o máximo divisor comum de dois números inteiros positivos consiste em substituir o número maior pela diferença entre os números e repetir isso até que os dois números sejam iguais: esse é o máximo divisor comum deles.

Exemplo: MDC(6, 15) = MDC(6, 15 - 6) = MDC(6, 9) = MDC(6, 9 - 6) = MDC(6, 3) = MDC(6 - 3, 3) = MDC(3, 3) = 3

Desafio

Fácil

Escreva um código em python, gcd, que recebe um vetor de dois números inteiros, v, e encontra o MDC (Máximo Divisor Comum) para esses dois números fornecidos.

Por favor, note que v[0] <= v[1].

Experimente você mesmo

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