Наименьшее кратное
2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?
Для начала посмотрим, как получилось это в случае с диапазоном от 1 до 10. Если просто перемножить их, получится 3628800. Слегка отличается от 2520. Зайдём с другой стороны и разложим 2520 на простые множители. Получится 2^3 * 3^2 * 5 * 7.
Теперь разложим на простые множители числа от 1 до 10. 1, 2, 3, 5 и 7 – простые числа сами по себе. 4 = 2^2, 6 = 2*3, 8 = 2^3, 9 = 3^2, 10 = 2*5. Становится понятно, что простые множители и их наибольшие степени в диапазоне от 1 до 10 совпадают с таковыми у числа 2520. Осталось научить алгоритм проделывать аналогичные операции.
Так как хочу создать программу, работающую для любых чисел (а в функцию всё засовывать не хочу), создадим сначала переменную, которая будет отвечать за верхнюю границу диапазона чисел, для которых нужно найти наименьшее общее кратное.
given_number = 20
Теперь создадим словарик, в котором данные будут в формате “число”:“его наибольшая степень” и заполним его нулями.
simple_numbers_power_dict = {}
for i in range(1, given_number+1):
simple_numbers_power_dict.setdefault(i, 0)
Теперь используем немного преобразованный алгоритм из 3 задачи для поиска всех простых делителей чисел в диапазоне.
for number in range(2, given_number+1):
list_of_dividers = []
divider = 2
while divider <= number:
while not number % divider:
number //= divider
list_of_dividers.append(divider)
divider += 1
for number in set(list_of_dividers): # Незначительно ускоряет работу,
# так как отсеивает
# повторяющиеся числа
simple_numbers_power_dict[number] = max(simple_numbers_power_dict[number], list_of_dividers.count(number))
Осталось только возвести числа из словаря в нужные степени и перемножить их.
answer = 1
for number in simple_numbers_power_dict.keys():
answer *= number** simple_numbers_power_dict[number]
print(answer)
Итоговый код:
given_number = 20
simple_numbers_power_dict = {}
for i in range(1, given_number+1):
simple_numbers_power_dict.setdefault(i, 0)
for number in range(2, given_number+1):
list_of_dividers = []
divider = 2
while divider <= number:
while not number % divider:
number //= divider
list_of_dividers.append(divider)
divider += 1
for number in set(list_of_dividers):
simple_numbers_power_dict[number] = max(simple_numbers_power_dict[number], list_of_dividers.count(number))
answer = 1
for number in simple_numbers_power_dict.keys():
answer *= number**simple_numbers_power_dict[number]
print(answer)
# Output: 232792560
