Задание 25 КЕГЭ: ищу делители, но программа считает слишком долго — как ускорить?
В задании 25 надо найти числа в диапазоне (например, от 150000 до 200000), у которых ровно N делителей или которые делятся на что-то определённое. Я считаю количество делителей циклом for d in range(1, n+1), и на большом диапазоне программа думает целую вечность. Как сделать быстро?
2 ответа
Цикл до n для каждого числа — это медленно (миллиарды операций). Главный приём задания 25: искать делители только до корня из n.
def delители(n):
res = []
d = 1
while d * d <= n: # только до sqrt(n)
if n % d == 0:
res.append(d)
if d != n // d:
res.append(n // d)
d += 1
return sorted(res)
for n in range(150000, 200001):
if len(delители(n)) == 5: # пример: ровно 5 делителей
print(n, delители(n))
Почему до корня: делители идут парами d и n//d. Если нашёл маленький d, то большой n//d получаешь бесплатно. Поэтому достаточно дойти до sqrt(n), а не до n. Это ускоряет в сотни раз и спокойно укладывается в тайм-лимит.
Не забудь про if d != n // d — иначе для полного квадрата корень посчитается дважды.
Если в задании 25 нужно вывести числа в порядке возрастания и в две колонки (само число и делитель/что-то ещё) — собирай результаты в список, потом отсортируй и выведи. И внимательно читай формат вывода: иногда просят не количество делителей, а конкретный делитель из заданного диапазона. Алгоритм с корнем тот же, меняется только условие отбора.