Introduction

Lesson 10 of 20 in Coddy's Mathematical Riddles course.

The greatest common divisor (GCD), of two positive integers x and y is the largest divisor common to x and y.

For example,

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

The greatest common divisor can also be defined for three or more positive integers as the largest divisor shared by all of them. Two or more positive integers that have greatest common divisor 1 are said to be relatively prime to one another. [Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Euclid's algorithm to find GCD

The method introduced by Euclid for computing greatest common divisors is based on the fact that, given two positive integers x and y such that y > x, the common divisors of x and y are the same as the common divisors of y - x and x.

So, Euclid's method for computing the greatest common divisor of two positive integers consists of replacing the larger number by the difference of the numbers, and repeating this until the two numbers are equal: that is their greatest common divisor.

Example: 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

Challenge

Easy

Write python code, gcd, that receives a vector of two integers, v, and finds the GCD for those two given numbers.

Please note that v[0] <= v[1].

Try it yourself

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