Introduction

Coddy'nin Matematiksel Bilmeceler kursunda ders 10 / 20.

İki pozitif tam sayı olan x ve y'nin en büyük ortak böleni (GCD), x ve y için ortak olan en büyük bölendir.

Örneğin,

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

En büyük ortak bölen, üç veya daha fazla pozitif tam sayı için de hepsinin paylaştığı en büyük bölen olarak tanımlanabilir. En büyük ortak böleni 1 olan iki veya daha fazla pozitif tam sayının birbirine göre aralarında asal olduğu söylenir. [Weisstein, Eric W. "Greatest Common Divisor." MathWorld'den--Bir Wolfram Web Kaynağı. https://mathworld.wolfram.com/GreatestCommonDivisor.html]

GCD bulmak için Öklid algoritması

Öklid tarafından en büyük ortak bölenleri hesaplamak için sunulan yöntem, y > x olacak şekilde iki pozitif tam sayı x ve y verildiğinde, x ve y'nin ortak bölenlerinin y - x ve x'in ortak bölenleriyle aynı olduğu gerçeğine dayanır.

Bu nedenle, iki pozitif tam sayının en büyük ortak bölenini hesaplamak için Öklid yöntemi, büyük sayıyı sayıların farkıyla değiştirmekten ve bu işlemi iki sayı eşit olana kadar tekrarlamaktan oluşur: bu onların en büyük ortak bölenidir.

Örnek: 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

Görev

Kolay

İki tam sayıdan oluşan bir v vektörü alan ve bu iki sayının OBEB'ini (GCD) bulan gcd adında bir Python kodu yazın.

Lütfen v[0] <= v[1] olduğunu unutmayın.

Kendin dene

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