@DarCKoder

Как оптимизировать алгоритм для выполнения 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.
Возможно ли оптимизировать алгоритм?
  • Вопрос задан
  • 959 просмотров
Решения вопроса 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Задачу можно решить и без перебора.
Для начала, берёте все числа от 2 до 20 и раскладываете на простые множители.
Как-то так:
2 = 21
3 = 31
4 = 22
5 = 51
6 = 21·31
7 = 71
8 = 23
9 = 32
10 = 21·51
11 = 111
12 = 22·31
13 = 131
14 = 21·71
15 = 31·51
16 = 24
17 = 171
18 = 21·32
19 = 191
20 = 22·51
Затем берёте максимальные степени из всех разложений и перемножаете их:
24·32·51·71·111·131·171·191 = 232792560
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Так зачем вы перебираете итератор по 1?
Найдите все простые числа <= limit и перемножте. Итератор увеличивайте на это произведение.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы