Question

Задача на C++ Нужно написать программу наибольший общий делитель и наименьшее общее кратное двух чисел

Answer 1

Ответ:

#include<bits/stdc++.h>

using ll = long long;

using namespace std;

#define endl '\n'

int gcd (int a, int b) {//НОД

return b ? gcd (b, a % b) : a;

}

int lcm (int a, int b) {//вычисление НОК также можно сделать с помощью алгоритма Евклида:

return a / gcd (a, b) * b;

}

int main()

{

   ll a, b;

   cin>>a>>b;

   cout<<gcd(a, b)<<endl;//НОД

   cout<<lcm(a, b)<<endl;//НОК

   return 0;

}

Answer 2

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

Нахождение НОД

Алгоритм Евклида основан на следующем принципе: НОД(a, b) = НОД(b, a % b), где % обозначает операцию взятия остатка от деления. Этот алгоритм позволяет находить НОД двух чисел за конечное количество шагов.

Вот пример программы на C++, которая находит НОД двух чисел:

#include

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int num1, num2;
    std::cout << "Введите два числа: ";
    std::cin >> num1 >> num2;
    int result = gcd(num1, num2);
    std::cout << "Наибольший общий делитель: " << result << std::endl;
    return 0;
}

Нахождение НОК

Наименьшее общее кратное (НОК) двух чисел можно найти с помощью формулы: НОК(a, b) = (a * b) / НОД(a, b).

Вот пример программы на C++, которая находит НОК двух чисел, используя функцию НОД из предыдущего примера:

#include

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    int gcdResult = gcd(a, b);
    int lcmResult = (a * b) / gcdResult;
    return lcmResult;
}

int main() {
    int num1, num2;
    std::cout << "Введите два числа: ";
    std::cin >> num1 >> num2;
    int result = lcm(num1, num2);
    std::cout << "Наименьшее общее кратное: " << result << std::endl;
    return 0;
}

Вы можете запустить эти программы, введя два числа, для которых вы хотите найти НОД и НОК. Программа выведет результат на экран.

Примечание: Обратите внимание, что эти программы предполагают, что вводимые числа являются целыми числами. Если вам нужно работать с дробными числами, вам потребуется использовать другие алгоритмы и методы.

Надеюсь, эта информация поможет вам решить задачу на C++! Если у вас возникнут еще вопросы, не стесняйтесь задавать их.