Introduction

Урок 10 из 20 курса Математические головоломки на Coddy.

Наибольший общий делитель (GCD) двух положительных целых чисел x и y — это самый большой делитель, общий для x и y.

Например,

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

Наибольший общий делитель также может быть определен для трех или более положительных целых чисел как самый большой делитель, общий для всех них. Два или более положительных целых числа, наибольший общий делитель которых равен 1, называются взаимно простыми. [Вайсштейн, Эрик В. «Наибольший общий делитель». Из MathWorld — веб-ресурса Wolfram. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Алгоритм Евклида для нахождения GCD

Метод, предложенный Евклидом для вычисления наибольших общих делителей, основан на том факте, что для двух положительных целых чисел x и y, таких что y > x, общие делители x и y совпадают с общими делителями y - x и x.

Таким образом, метод Евклида для вычисления наибольшего общего делителя двух положительных целых чисел заключается в замене большего числа разностью этих чисел и повторении этого процесса до тех пор, пока два числа не станут равными: это и есть их наибольший общий делитель.

Пример: 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

Задание

Легко

Напишите код на python, функцию gcd, которая получает вектор из двух целых чисел, v, и находит НОД (наибольший общий делитель) для этих двух заданных чисел.

Обратите внимание, что v[0] <= v[1].

Попробуйте сами

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