Question

На вход программы поступает последовательность из N целых положительных чисел. Необходимо найти их наименьшее общее кратное. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (2 \leq N \leq 20). В каждой из последующих N строк записано одно положительное целое число, не превышающее 10000 В качестве результата программа должна напечатать наименьшее общее кратное данных N чисел. Пример входных данных: 3 12 4 24 Пример выходных данных для приведённого выше примера входных данных: 24 Требуется написать эффективную по времени и памяти программу.

Answer 1

Ответ:

Код на Python, у меня получилось так. Не знаю, что насчет эффективности, но код рабочий

Answer 2

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

1. Сначала импортируем библиотеку math для использования функции gcd (наибольший общий делитель).

2. Считываем количество чисел N.

3. Инициализируем переменную lcm (наименьшее общее кратное) равной первому числу из последовательности.

4. Для каждого следующего числа в последовательности:

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

5. После завершения цикла, переменная lcm будет содержать НОК для всех чисел.

6. Выводим значение lcm как результат.

Вот Python-код, который реализует этот алгоритм:

pythonCopy code
import math

# Считываем количество чисел N
N = int(input())

# Инициализируем lcm равным первому числу
lcm = int(input())

# Вычисляем НОК для остальных чисел
for _ in range(1, N):
    num = int(input())
    gcd = math.gcd(lcm, num)
    lcm = (lcm * num) // gcd

# Выводим наименьшее общее кратное
print(lcm)

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

Copy code
3
12
4
24

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

Copy code
24

Этот код эффективен как по времени, так и по памяти, и способен обрабатывать даже большие последовательности чисел.