Алгоритм Евклида, расширенный алгоритм Евклида на C

June 10, 2019 22:53

Алгоритм Евклида - это алгоритм поиска наибольшего общего делителя двух целых чисел. Обычно алгоритм Евклида используется на паре чисел и создает новую пару, состоящую из меньшего числа и разницы между большим и меньшим числом. Далее действия повторяются до тех пор, пока числа не станут равными. Число, полученное в результате является наибольшим общим делителем исходной пары.

Ниже представлена реализация алгоритма Евклида и расширенного алгоритма Евклида на си (C).

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

/*    
*   Алгоритм Евклида (нахождение наибольшего общего делителя)
*/
long gcd(long a, long b) {
    if (a < b) {
        return gcd(b, a);
    }

    while (b != 0) {
        long temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

/*
*  Расширенный Алгоритм Евклида (нахождение коэфициентов x, y, таких что ax + by = gcd(a, b))
*/
void gcd_ext(long a, long b, long *x, long *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;

        return;
    }

    gcd_ext(b, a % b, x, y);

    long temp = *y;
    *y = *x - (*y) * (a / b);
    *x = temp;
}


int main(int argc, char *argv[]) {
    if (argc == 3) {
        printf("%ld", gcd(atol(argv[1]), atol(argv[2])));
        return 0;
    }

    if (argc == 4 && strncmp(argv[1], "-e", 2) == 0) {
        long x = 0, y = 0;
        gcd_ext(atol(argv[2]), atol(argv[3]), &x, &y);
        
        printf("%ld %ld", x, y);
        return 0;
    }

    printf("Usage: \n\t%s [-e] <%ld..%ld> <%ld..%ld>\n", argv[0], LONG_MIN, LONG_MAX, LONG_MIN, LONG_MAX);
    return 1;
}