Как оптимизировать алгоритм для выполнения 5 задачи с проекта Эйлера?

Question

[Umid]

Добрый день!
Написал алгоритм для реализации вот этой задачи.

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.
Возможно ли оптимизировать алгоритм?

Answer 1

[Rsa97]

Задачу можно решить и без перебора.
Для начала, берёте все числа от 2 до 20 и раскладываете на простые множители.

Как-то так:

2 = 2¹
3 = 3¹
4 = 2²
5 = 5¹
6 = 2¹·3¹
7 = 7¹
8 = 2³
9 = 3²
10 = 2¹·5¹
11 = 11¹
12 = 2²·3¹
13 = 13¹
14 = 2¹·7¹
15 = 3¹·5¹
16 = 2⁴
17 = 17¹
18 = 2¹·3²
19 = 19¹
20 = 2²·5¹

Затем берёте максимальные степени из всех разложений и перемножаете их:
2⁴·3²·5¹·7¹·11¹·13¹·17¹·19¹ = 232792560

Answer 2

[Andrey Shatokhin]

Так зачем вы перебираете итератор по 1?
Найдите все простые числа <= limit и перемножте. Итератор увеличивайте на это произведение.

Comments

[Сергей Соколов]

если перемножить все простые до 10 получится 210, что меньше 2520, которое является правильным ответом.

[Andrey Shatokhin]

Сергей Соколов: если перемножить все простые числа до 10 то получится 42, а не 210. И это не ответ. Это произведение нужно использовать вместо 1 вот тут
> iterator += 1

[Сергей Соколов]

Андрей: 2 * 3 * 5 * 7 = 210

[Andrey Shatokhin]

Сергей Соколов: Да. тут вы правы