Question

Наибольший общий делитель двух натуральных чисел – наибольшее число, на которое делятся данные числа. Наименьшее общее кратное двух натуральных чисел – наименьшее число, которое делится на данные числа. На вход программы поступают 2 целых положительных числа. Необходимо найти их наибольший общий делитель и наименьшее общее кратное. Описание входных и выходных данных В двух строках по одному записаны натуральные числа, не превосходящие 100000000. В качестве результата программа должна напечатать через пробел наибольший общий делитель и наименьшее общее кратное данных чисел. Пример входных данных: 12 16 Пример выходных данных для приведённого выше примера входных данных: 4 48 Требуется написать эффективную по времени и памяти программу. Перед текстом программы обязательно опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Answer 1

program krolik;

var a,b,i,del,kr,p:longint;

begin

writeln('введите значение первого числа');

readln(a);

writeln('введите значение второго числа');

readln(b);

if (a<=0) or (b<=0) then

writeln('ошибка');

del:=1;

for i:=1 to a do

if (a mod i=0) and (b mod i=0) then

del:=i;

p:=a*b;

kr:=p;

for i:=p downto 1 do

if (i mod a=0) and (i mod b=0) then

kr:=i;

writeln(del,' ',kr);

end.

Answer 2

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

1. Считайте два натуральных числа, например, a и b.

2. Выполните алгоритм Евклида для нахождения НОД:

   • Пока b не станет равным нулю, делайте следующее:
     • Вычислите остаток от деления a на b: r = a % b.
     • Переместите b в a и r в b: a = b, b = r.
   • Когда b станет равным нулю, значение a будет НОД(a, b).

3. Вычислите НОК с использованием формулы: НОК = (a * b) / НОД.

Программа на Python:

pythonCopy code
def find_gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def find_lcm(a, b):
    gcd = find_gcd(a, b)
    lcm = (a * b) // gcd
    return lcm

# Ввод чисел
a, b = map(int, input().split())

# Нахождение НОД и НОК
gcd = find_gcd(a, b)
lcm = find_lcm(a, b)

# Вывод результатов
print(gcd, lcm)

Этот код сначала находит НОД с использованием алгоритма Евклида, а затем вычисляет НОК с использованием формулы. После ввода чисел программа выводит НОД и НОК через пробел.

Пример работы программы:

makefileCopy code
Ввод:
12 16

Вывод:
4 48

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