Как оптимизировать алгоритм для выполнения 5 задачи с проекта Эйлера? Добрый день!
Написал алгоритм для реализации вот этой задачи.def euler5(limit):
hasNumberFound = False
iterator = 1
while not hasNumberFound:
num = limit * iterator
for divider in range(2, limit):
if num % divider != 0:
break
else:
hasNumberFound = True
return num
iterator += 1
print( euler5(20) )
Смущает то, что на выполнение задачи при значении аргумента функции равной 20, уходит 13.5 секунд. На выходе выдаёт: 232792560.
Возможно ли оптимизировать алгоритм?
Как оптимизировать алгоритм для выполнения 5 задачи с проекта Эйлера? Добрый день!
Написал алгоритм для реализации вот этой задачи.def euler5(limit):
hasNumberFound = False
iterator = 1
while not hasNumberFound:
num = limit * iterator
for divider in range(2, limit):
if num % divider != 0:
break
else:
hasNumberFound = True
return num
iterator += 1
print( euler5(20) )
Смущает то, что на выполнение задачи при значении аргумента функции равной 20, уходит 13.5 секунд. На выходе выдаёт: 232792560.
Возможно ли оптимизировать алгоритм?
Написал алгоритм для реализации вот этой задачи.def euler5(limit):
hasNumberFound = False
iterator = 1
while not hasNumberFound:
num = limit * iterator
for divider in range(2, limit):
if num % divider != 0:
break
else:
hasNumberFound = True
return num
iterator += 1
print( euler5(20) )
Смущает то, что на выполнение задачи при значении аргумента функции равной 20, уходит 13.5 секунд. На выходе выдаёт: 232792560.
Возможно ли оптимизировать алгоритм?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Да, можно оптимизировать данный алгоритм. Вместо того, чтобы проверять все числа от 1 до limit * iterator, можно воспользоваться математическими свойствами и найти наименьшее общее кратное (НОК) всех чисел от 1 до limit.
Вот оптимизированный алгоритм:
def gcd(a, b):while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
def euler5(limit):
result = 1
for i in range(1, limit + 1):
result = lcm(result, i)
return result
print(euler5(20))
Этот алгоритм работает значительно быстрее и может решить задачу для аргумента 20 мгновенно. Результат остается тем же: 232792560.