Introduction

Leçon 10 sur 20 du cours Énigmes mathématiques de Coddy.

Le plus grand commun diviseur (GCD) de deux entiers positifs x et y est le plus grand diviseur commun à x et y.

Par exemple,

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

Le plus grand commun diviseur peut également être défini pour trois entiers positifs ou plus comme le plus grand diviseur partagé par tous. Deux entiers positifs ou plus qui ont un plus grand commun diviseur de 1 sont dits premiers entre eux. [Weisstein, Eric W. "Greatest Common Divisor." Tiré de MathWorld--Une ressource Web Wolfram. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Algorithme d'Euclide pour trouver le GCD

La méthode introduite par Euclide pour calculer les plus grands communs diviseurs est basée sur le fait que, étant donné deux entiers positifs x et y tels que y > x, les diviseurs communs de x et y sont les mêmes que les diviseurs communs de y - x et x.

Ainsi, la méthode d'Euclide pour calculer le plus grand commun diviseur de deux entiers positifs consiste à remplacer le plus grand nombre par la différence des nombres, et à répéter cela jusqu'à ce que les deux nombres soient égaux : c'est leur plus grand commun diviseur.

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

Défi

Facile

Écrivez un code python, gcd, qui reçoit un vecteur de deux entiers, v, et trouve le PGCD de ces deux nombres donnés.

Veuillez noter que v[0] <= v[1].

Essayez vous-même

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