Задание 25 ЕГЭ: как искать числа с нужным количеством делителей перебором?
В 25-м часто просят: найти в диапазоне числа, у которых ровно N делителей, или у которых наибольший делитель (кроме самого числа) обладает свойством. Перебор делителей до самого числа жутко медленный на больших диапазонах. Как ускорить и не упереться в тайм-лимит?
4 ответа
Перебирай делители только до корня числа — для каждого найденного делителя d сразу учитывай парный n//d. Это ускоряет в десятки раз и в тайм-лимит укладывается легко.
def divisors(n):
res = []
i = 1
while i * i <= n:
if n % i == 0:
res.append(i)
if i != n // i:
res.append(n // i)
i += 1
return sorted(res)
for n in range(174000, 200000):
d = divisors(n)
if len(d) == 6: # ровно 6 делителей — условие из задачи
print(n, d[-2]) # например, второй по величине делитель
Ходишь while i*i <= n вместо range(1, n) — вот и весь секрет скорости. Для «наибольшего делителя кроме самого числа» это n // (наименьший простой делитель).
Перебор делителей только до √n, парный добавляешь как n//i. range(1,n) — это и есть твой тайм-лимит.
До корня квадратного.
Бери sympy.divisors, чего велосипед изобретать.
