Оптимизация функции поиска делителей числа
задача найти количество чисел, строго больших, чем b, на которые делится число n. Я написал простейшую функцию:
def get_ls(n, b):
i = b+1
k = 0
while i <= n:
if (n%i==0):
k += 1
i += 1
else:
i += 1
return k
Но, разумеется, она работает очень медленно. Можете, пожалуйста, предложить способы по её ускорению? Заранее спасибо.
Ответы (1 шт):
Автор решения: Zhihar
→ Ссылка
по идее надо делать так:
import math
def get_ls(n, b):
count = 0
for i in range(1, int(math.sqrt(n + 1)) + 1):
if n % i == 0:
count += 1 if i > b else 0
count += 1 if n // i > b else 0
return count
print(get_ls(123456789098765, 4321)) # res = 12, работает около 2-3 сек
основная идея -
нам не надо рассматривать все числа от
bдоnнам надо рассмотреть только числа от
1доsqrt(n)учитывать надо 2 множителя -
iиn // iи смотреть какие из них больше b
в итоге сложность задачи не O(n), а O(sqrt(n))
P.S.
код писал на коленке, по идее его можно еще чуть-чуть пооптимизировать, но основной прирост скорости реализован