Ускорьте работу кода

Question

Назовём натуральное число подходящим, если у него больше 17 различных делителей (включая единицу и само число). Определите количество подходящих чисел, принадлежащих отрезку [10 001; 50 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

sp = []
k=0
m=50001
for i in range(10001,50001):
    for j in range(1,i//2+1):
        if i%j==0:
            sp.append(j)
    if len(sp)>16:
        k+=1
        if i<m:
            m=i
    sp.clear()
print(k,m)

выводит ответ очень долго, что не дождаться

код добавляет все делители числа в список и потом если длин списка >16(хотя в условии сказано 17, но для того чтобы как то ускорить выше в делителях я сделал ограничение до половины числа, ибо дальше только делитель это само число, соответственно его в списке только не будет и значит в условии на один меньше)

как мог ускорил, но все равно не получается

Answer 1

Не до половины числа, а до корня из числа
Добавлять в список можно не только сам делитель, но и результат деления числа на этот делитель, ведь это тоже делитель (исключая случай, когда они совпадают, т.е. когда делитель равен корню из числа)
Проверять на то, что набралось нужное количество чисел, можно не дожидаясь прохода по всему диапазону делителей, за счёт этого можно досрочно прервать цикл в каких-то случаях

Приходим к такому коду:

sp = set()
k=0
m=50001
for i in range(10001,50001):
    for j in range(1,int(i**0.5)+1):
        if i%j==0:
            sp.add(j)
            sp.add(i//j)
            if len(sp)>17:
                k+=1
                if i<m:
                    m=i
                break
    sp.clear()
print(k,m)

Я использую set, а не list только для того, чтобы не проверять является ли делитель корнем числа. В set число добавится только один раз, он об этом позаботится.

БЛОГ НА HUSL

Ускорьте работу кода

Ответы (1 шт):