Как найти наименьшее общее кратное (НОК) в C

Введение

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

Чтение двух целых чисел

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

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

cd ~/project
nano lcm.c

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

#include <stdio.h>

int main() {
    int a, b;

    printf("Введите два положительных целых числа:\n");
    printf("Первое число: ");
    scanf("%d", &a);

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

    printf("Вы ввели: %d и %d\n", a, b);

    return 0;
}

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

gcc lcm.c -o lcm
./lcm

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

Введите два положительных целых числа:
Первое число: 12
Второе число: 18
Вы ввели: 12 и 18

Давайте разберем код:

Функция scanf() используется для чтения целых чисел из пользовательского ввода.
Спецификатор формата %d используется для ввода целых чисел.
&a и &b передают адреса памяти, где будут храниться введенные значения.

Использование формулы НОК = (a*b)/НОД(a,b)

В этом шаге вы реализуете вычисление наименьшего общего кратного (НОК) с использованием формулы НОК(a,b) = (a*b)/НОД(a,b). Сначала мы создадим функцию для вычисления наибольшего общего делителя (НОД) с помощью алгоритма Евклида.

Обновите файл lcm.c следующим кодом:

#include <stdio.h>

// Функция для вычисления НОД с помощью алгоритма Евклида
int calculateGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Функция для вычисления НОК
int calculateLCM(int a, int b) {
    return (a * b) / calculateGCD(a, b);
}

int main() {
    int a, b, lcm;

    printf("Введите два положительных целых числа:\n");
    printf("Первое число: ");
    scanf("%d", &a);

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

    lcm = calculateLCM(a, b);

    printf("Наименьшее общее кратное %d и %d равно: %d\n", a, b, lcm);

    return 0;
}

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

gcc lcm.c -o lcm
./lcm

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

Введите два положительных целых числа:
Первое число: 12
Второе число: 18
Наименьшее общее кратное 12 и 18 равно: 36

Давайте разберем ключевые компоненты:

calculateGCD() реализует алгоритм Евклида для нахождения наибольшего общего делителя.
calculateLCM() использует формулу НОК(a,b) = (a*b)/НОД(a,b).
Алгоритм Евклида эффективно находит НОД, многократно вычисляя остаток.

Вывод НОК

В этом заключительном шаге вы запустите программу вычисления НОК и проверите её вывод для различных комбинаций входных данных. Мы протестируем программу с различными парами целых чисел, чтобы продемонстрировать вычисление НОК.

Скомпилируйте программу (если она ещё не скомпилирована):

cd ~/project
gcc lcm.c -o lcm

Запустите программу с различными комбинациями входных данных:

./lcm << EOF
12
18
EOF

Пример вывода для 12 и 18:

Введите два положительных целых числа:
Первое число: 12
Второе число: 18
Наименьшее общее кратное 12 и 18 равно: 36

Попробуем другой пример:

./lcm << EOF
15
25
EOF

Пример вывода для 15 и 25:

Введите два положительных целых числа:
Первое число: 15
Второе число: 25
Наименьшее общее кратное 15 и 25 равно: 75

Ключевые моменты:

НОК — это наименьшее положительное целое число, которое делится на оба входных числа.
Для 12 и 18 НОК равно 36.
Для 15 и 25 НОК равно 75.
Программа использует формулу НОК(a,b) = (a*b)/НОД(a,b).

Для повышения надёжности программы можно добавить проверку входных данных:

nano lcm.c

Обновите функцию main() для включения проверки входных данных:

int main() {
    int a, b, lcm;

    printf("Введите два положительных целых числа:\n");
    printf("Первое число: ");
    scanf("%d", &a);

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

    // Проверка входных данных
    if (a <= 0 || b <= 0) {
        printf("Ошибка: Пожалуйста, введите только положительные целые числа.\n");
        return 1;
    }

    lcm = calculateLCM(a, b);

    printf("Наименьшее общее кратное %d и %d равно: %d\n", a, b, lcm);

    return 0;
}

Перекомпилируйте и протестируйте обновлённую программу:

gcc lcm.c -o lcm
./lcm

Резюме

В этом лабораторном практикуме вы научитесь находить наименьшее общее кратное (НОК) двух целых чисел на языке C. Сначала вы будете считывать два целых числа с пользовательского ввода. Затем вы реализуете формулу НОК(a,b) = (a*b)/НОД(a,b), создав функцию для вычисления наибольшего общего делителя (НОД) с помощью алгоритма Евклида. Наконец, вы выведете вычисленное НОК.

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

Нахождение наименьшего общего кратного (НОК) в C

Введение

Чтение двух целых чисел

Использование формулы НОК = (a*b)/НОД(a,b)

Вывод НОК

Резюме