Задача CSES Counting Divisors

Question

Задача с сайта CSES Задачу решаю верно, но при проведении некоторых тестов пишет, что время выполнения превышено. Как можно оптимизировать код?

divs = 0
divs_count = []
div_list = []
n = int(input())
i = 0
while n > i and 10*n**6 >= n >= 1:
  x = int(input())
  if 10*x**6 >= x >= 1:
    div_list.append(x)
  i += 1

g = 0
while g < len(div_list): 
    i = div_list[g]
    divs = 0
    while i > 0:
        if div_list[g] % i == 0:
            divs += 1
        i -= 1
    divs_count.append(str(divs))
    g += 1  
print('\n'.join(divs_count))

Answer 1

наивное решение O(sqrt(n)):

def count_divisors(num):
    divisors = set()
    square = num ** 0.5
    for divisor in range(1, int(square) + 1):
        if num % divisor == 0:
            divisors.add(divisor)
            divisors.add(num // divisor)

    return len(divisors)

def main():
    n = int(input('n: '))
    for i in range(n):
        num = int(input('num: '))
        print(count_divisors(num))

if __name__ == '__main__':
    main()

Update:

для быстрого решения есть ответ здесь: https://ru.stackoverflow.com/questions/562346/Количество-делителей-числа

Answer 2

Код решения задачи:

# если число разложить в виде произведения простых чисел (например, 24 = 2^3 * 3),то количеством делителей будет произведение всех степеней, увеличенных на 1. В данном случае кол-вом делителей числа 24 будет (3 + 1) * (1 + 1) = 4 * 2 = 8.

def count_of_divisors(n):
    a = []
    d_counter = 0
    mult = 1
    d = 2   # начальный делитель - 2 (т.к. самое маленькое простое число - 2)
    while d * d <= n:   # пока d <= √n
        while n % d == 0:   # пока n делится на d
            n //= d     # делим n на делитель
            d_counter += 1  # инкрементируем степень (количество) делителя
        mult *= d_counter + 1
        d_counter = 0   # обнуляем цикл по окончании вложенного цикла
        d += 1  # инкрементируем делитель
    if n > 1: # если n ещё не равно 1, то n - простое, и оно делится только на себя (и на 1)
        mult *= 2
    return mult

БЛОГ НА HUSL

Задача CSES Counting Divisors

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