Euclidean algorithm

Coddy의 수학 수수께끼 코스 레슨 — 20개 중 11번째.

더 효율적인 방법은 두 수 x와 y의 차이를 y를 x로 나눈 나머지로 대체하는 방식인 유클리드 호제법(Euclidean algorithm)입니다.

이 나머지를 y mod x라고 하면, 이 알고리즘은 쌍이 (0, d)가 될 때까지 (x, y)를 (x, y mod x)로 반복해서 교체하며, 여기서 d는 최대공약수입니다.

챌린지

중급

두 개의 숫자가 포함된 벡터 v를 받아 유클리드 호제법을 기반으로 최대공약수(GCD)를 계산하는 파이썬 코드 gcd2를 작성하세요.

이 코드는 일반적인 유클리드 알고리즘과 비교했을 때 얼마나 더 빠릅니까?

직접 해보기

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