Нахождение наибольшего общего делителя (НОД) в C

Введение

В этом лабораторном практикуме вы научитесь находить наибольший общий делитель (НОД) двух целых чисел с помощью алгоритма Евклида в программе на языке C. Вы начнете с ввода двух целых чисел от пользователя, затем примените алгоритм Евклида для вычисления их НОД и, наконец, выведете результат. Этот практикум охватывает фундаментальные понятия теории чисел и дискретной математики, предоставляя практическое применение этих принципов с использованием языка программирования C.

Ввод двух целых чисел

В этом шаге вы узнаете, как ввести два целых числа от пользователя в программе на языке C для нахождения их наибольшего общего делителя (НОД).

Сначала создадим новый файл C для нашей программы вычисления НОД:

cd ~/project
nano gcd.c

Теперь добавим следующий код для ввода двух целых чисел:

#include <stdio.h>

int main() {
    int num1, num2;

    printf("Enter the first integer: ");
    scanf("%d", &num1);

    printf("Enter the second integer: ");
    scanf("%d", &num2);

    printf("First number: %d\n", num1);
    printf("Second number: %d\n", num2);

    return 0;
}

Рассмотрим код подробнее:

• scanf() используется для считывания целых чисел от пользователя
• %d — спецификатор формата для целых чисел
• &num1 и &num2 передают адреса памяти переменных для хранения введённых данных

Компилируем и запускаем программу:

gcc gcd.c -o gcd
./gcd

Пример вывода:

Enter the first integer: 48
Enter the second integer: 18
First number: 48
Second number: 18

Применение алгоритма Евклида

В этом шаге вы реализуете алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух целых чисел.

Откройте предыдущий файл gcd.c и измените его, включив в него вычисление НОД:

cd ~/project
nano gcd.c

Обновите код, добавив реализацию алгоритма Евклида:

#include <stdio.h>

// Функция для вычисления НОД с помощью алгоритма Евклида
int calculateGCD(int a, int b) {
    // Обеспечение положительных чисел
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Алгоритм Евклида
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Enter the first integer: ");
    scanf("%d", &num1);

    printf("Enter the second integer: ");
    scanf("%d", &num2);

    // Вычисление НОД
    gcd = calculateGCD(num1, num2);

    printf("First number: %d\n", num1);
    printf("Second number: %d\n", num2);
    printf("Greatest Common Divisor: %d\n", gcd);

    return 0;
}

Рассмотрим реализацию алгоритма Евклида:

• Алгоритм многократно делит большее число на меньшее.
• Он использует оператор взятия остатка %, чтобы получить остаток.
• Процесс продолжается до тех пор, пока остаток не станет равным 0.
• Последний ненулевой остаток — это НОД.

Компилируем и запускаем программу:

gcc gcd.c -o gcd
./gcd

Пример вывода:

Enter the first integer: 48
Enter the second integer: 18
First number: 48
Second number: 18
Greatest Common Divisor: 6

Вывод НОД

В этом шаге вы отформатируете и выведете результат вычисления НОД с дополнительным контекстом, чтобы сделать вывод более информативным.

Откройте предыдущий файл gcd.c и добавьте форматирование вывода:

cd ~/project
nano gcd.c

Обновите код для улучшения вывода НОД:

#include <stdio.h>

// Функция для вычисления НОД с помощью алгоритма Евклида
int calculateGCD(int a, int b) {
    // Обеспечение положительных чисел
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Алгоритм Евклида
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Калькулятор наибольшего общего делителя (НОД)\n");
    printf("----------------------------------------\n");

    printf("Введите первое целое число: ");
    scanf("%d", &num1);

    printf("Введите второе целое число: ");
    scanf("%d", &num2);

    // Вычисление НОД
    gcd = calculateGCD(num1, num2);

    // Отформатированный вывод
    printf("\nРезультаты:\n");
    printf("Первое число:  %d\n", num1);
    printf("Второе число: %d\n", num2);
    printf("НОД:           %d\n", gcd);

    // Дополнительное объяснение
    printf("\nОбъяснение:\n");
    printf("Наибольший общий делитель (НОД) — это наибольшее положительное целое число,\n");
    printf("которое делит оба числа без остатка.\n");

    return 0;
}

Компилируем и запускаем программу:

gcc gcd.c -o gcd
./gcd

Пример вывода:

Калькулятор наибольшего общего делителя (НОД)
----------------------------------------
Введите первое целое число: 48
Введите второе целое число: 18

Результаты:
Первое число:  48
Второе число: 18
НОД:           6

Объяснение:
Наибольший общий делитель (НОД) — это наибольшее положительное целое число,
которое делит оба числа без остатка.

Основные улучшения:

• Добавлено заголовок и разделитель
• Отформатирован вывод с выровненными столбцами
• Включено объяснение понятия НОД
• Сохранена основная логика вычисления НОД

Резюме

В этом лабораторном практикуме вы сначала изучили, как считывать два целых числа из пользовательского ввода с помощью функции scanf(). Затем вы реализовали алгоритм Евклида для вычисления наибольшего общего делителя (НОД) этих двух чисел. Алгоритм Евклида — эффективный способ нахождения НОД, заключающийся в многократном применении операции взятия остатка от деления до тех пор, пока остаток не станет равным нулю. В этот момент НОД равен последнему ненулевому остатку. Наконец, вы вывели вычисленный НОД.