Euclidean algorithm

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

Une méthode plus efficace est l'algorithme d'Euclide, une variante dans laquelle la différence des deux nombres x et y est remplacée par le reste de la division de y par x.

En notant ce reste y mod x, l'algorithme remplace (x, y) par (x, y mod x) de manière répétée jusqu'à ce que la paire soit (0, d), où d est le plus grand commun diviseur.

Défi

Moyen

Écrivez un code python, gcd2, qui calcule le PGCD, basé sur l'algorithme d'Euclide, qui reçoit un vecteur v avec deux nombres donnés.

À quel point ce code est-il plus rapide par rapport à l'algorithme d'Euclide ?

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