Pengantar

Pelajaran 10 dari 20 dalam kursus Teka-teki Matematika di Coddy.

Pembagi persekutuan terbesar (GCD) dari dua bilangan bulat positif x dan y adalah pembagi terbesar yang sama-sama membagi x dan y.

Contohnya,

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

Pembagi persekutuan terbesar juga dapat didefinisikan untuk tiga bilangan bulat positif atau lebih sebagai pembagi terbesar yang dimiliki bersama oleh semuanya. Dua bilangan bulat positif atau lebih yang memiliki pembagi persekutuan terbesar 1 dikatakan relatif prima satu sama lain. [Weisstein, Eric W. "Greatest Common Divisor." Dari MathWorld, Sumber Web Wolfram. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

Algoritma Euclid untuk mencari GCD

Cara yang diperkenalkan Euclid untuk menghitung pembagi persekutuan terbesar didasarkan pada fakta bahwa, jika diberikan dua bilangan bulat positif x dan y dengan y > x, pembagi yang sama dari x dan y juga merupakan pembagi yang sama dari y - x dan x.

Jadi, cara Euclid untuk menghitung pembagi persekutuan terbesar dari dua bilangan bulat positif dilakukan dengan mengganti bilangan yang lebih besar dengan selisih kedua bilangan, lalu mengulanginya sampai kedua bilangan sama: nilai tersebut adalah pembagi persekutuan terbesar keduanya.

Contoh: 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

Tantangan

Mudah

Tulis kode python, gcd, yang menerima vektor berisi dua bilangan bulat, v, dan mencari GCD dari kedua bilangan tersebut.

Harap diperhatikan bahwa v[0] <= v[1].

Coba sendiri

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