欧几里得算法

Coddy 数学谜题课程的第 11 课，共 20 课。

更高效的方法是欧几里得算法，它会用 y 除以 x 的余数替换两个数 x 和 y 的差。

将这个余数表示为 y mod x，算法会反复将 (x, y) 替换为 (x, y mod x)，直到这一对数变为 (0, d)，其中 d 是最大公约数。

挑战

中等

编写 Python 代码，实现 gcd2 函数，使用欧几里得算法计算最大公约数。该函数接收一个包含两个给定数字的向量 v。

与欧几里得算法相比，这段代码有多快？

亲手试试

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