Introduction

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

두 양의 정수 x와 y의 최대공약수(GCD)는 x와 y의 공통된 약수 중 가장 큰 수입니다.

예를 들어,

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

최대공약수는 셋 이상의 양의 정수에 대해서도 모든 정수가 공유하는 가장 큰 공약수로 정의될 수 있습니다. 최대공약수가 1인 둘 이상의 양의 정수들은 서로소(relatively prime)라고 합니다. [Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

GCD를 구하기 위한 유클리드 알고리즘

최대공약수를 계산하기 위해 유클리드가 도입한 방법은, y > x인 두 양의 정수 x와 y가 주어졌을 때, x와 y의 공약수는 y - x와 x의 공약수와 같다는 사실에 기반합니다.

따라서, 두 양의 정수의 최대공약수를 계산하는 유클리드 방법은 더 큰 수를 두 수의 차이로 바꾸고, 두 수가 같아질 때까지 이 과정을 반복하는 것으로 구성됩니다. 이때 같아진 수가 바로 그들의 최대공약수입니다.

예시: 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

챌린지

쉬움

두 개의 정수로 이루어진 벡터 v를 입력받아, 해당 두 숫자의 최대공약수(GCD)를 구하는 파이썬 코드 gcd를 작성하세요.

v[0] <= v[1]임에 유의하세요.

직접 해보기

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