Помогите решить задачу на языке Python пожалуйста!

Не знаю, что такое O(n−−√).
O(√n), может быть?

Тогда так:

 def factors(n):

    factors, p, inc = [], 2, 1

    while p * p  1: factors.append(n)

    return factors



print(*factors(int(input()))) 

Количество проверочных делений для простых чисел не превышает половины корня из числа + 1 (т.к. мы перебираем двойку и нечётные делители, начиная с тройки). Для составных чисел делений намного меньше, т.к. каждый найденный делитель d кратности k уменьшает диапазон для перебора в √(kd) раз.
Сложность деления 32-битных чисел считаем константой. Хотя, по факту это - экспонента от количества бит.

Можно снизить константный фактор ещё в 2 с лишним раза, отсеяв все составные делители до 210 и более трёх четвертей - после 210.

 from itertools import accumulate, chain, cycle



INITIAL = [2, 3, 5, 7]

NEXT = [11]

STEPS = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8,

         6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]



def factors(n):

    divs = chain(INITIAL, accumulate(chain(NEXT, cycle(STEPS))))

    factors, p = [], next(divs)

    while p * p  1: factors.append(n)

    return factors



print(*factors(int(input()))) 

Для простого числа 10000004873 (10 млрд) получится около 22860 делений, т.е. меньше четверти от его корня. Первоначальный алгоритм выдавал для него 50000 делений, т.е. почти половину от корня.

Максимальное простое число в пределах вашей верхней границы: 1999999817. Для него второй алгоритм выдаст 10226 делений, а первый - 22361. Вполне укладывается в асимптотику O(√n).

А если вам нужна сложность O(√n/(log n)), тогда смотрите решето Эратосфена.

А всё же интересно как ты собираешься сложность O(n−−√)
расчитывать в таком случае. В теории это всё конечно работает а на практике как?