Как быстро перебрать делители числа в задании 25 КЕГЭ (до корня)?
В 25-м задании часто надо для каждого числа из диапазона узнать количество делителей или найти конкретные делители. Если перебирать делители от 1 до N для каждого числа диапазона, на больших числах долго. Как ускорить перебор делителей?
4 ответа
Перебирай делители только до √N: если i делит N, то парный делитель N // i находится сразу. Это сокращает работу с O(N) до O(√N).
def divisors(n):
res = set()
i = 1
while i * i <= n:
if n % i == 0:
res.add(i)
res.add(n // i) # парный делитель
i += 1
return sorted(res)
Использую i * i <= n вместо i <= n**0.5, чтобы не связываться с погрешностью float. Для задания 25, где диапазон вроде 100000–200000, такой перебор по каждому числу проходит за доли секунды. Если нужно именно КОЛИЧЕСТВО делителей — считаешь len этого множества (или аккуратно ++2 за каждую пару, +1 для полного квадрата).
До корня: while i*i <= n. Нашёл i — сразу бери и n//i.
Если нужны ВСЕ числа диапазона с делителями — иногда быстрее решето: пробегаешь делителями и инкрементишь счётчики у кратных. Но для 25 обычно хватает и перебора до корня по каждому числу.
До √N.
