Thuật toán Euclid

Bài học 11 trên 20 trong khóa học Câu đố toán học của Coddy.

Một phương pháp hiệu quả hơn là thuật toán Euclid, một biến thể thay hiệu giữa hai số x và y bằng số dư của phép chia y cho x.

Ký hiệu số dư này là y mod x, thuật toán liên tục thay (x, y) bằng (x, y mod x) cho đến khi cặp số là (0, d), trong đó d là ước chung lớn nhất.

Thử thách

Trung bình

Viết code Python, gcd2, để tính ƯCLN bằng thuật toán Euclid, nhận một vector v gồm hai số cho trước.

Code này nhanh hơn thuật toán Euclid bao nhiêu?

Tự làm thử

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