1

Задача с сайта 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))

2 ответа 2

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/Количество-делителей-числа

5
  • У вас тоже решение правильное, но по времени выполнения не проходит некоторые тесты. Выдает TIME LIMIT EXCEEDED 30 июн 2020 в 19:16
  • @CyberGenius исправил
    – Ildar
    30 июн 2020 в 20:39
  • @Ildar, Здравствуйте! На сайте CSES я пробовал Ваше и моё решение, но почему-то они оба не проходят по времени, хотя наши решения теоретически верные. Я решал такое же задание на платформе Сириус, и там моё точно такое же решение прошло по времени (скорее всего, там тоже была 1 секунда). Мне кажется, проблема не в нашем решении, а в их сайте… 30 июн 2020 в 20:59
  • 1
    @DaniilSavinov здравствуйте, есть более быстрое решение с лучшей асимптотикой которое описано в ссылке пониже
    – Ildar
    1 июл 2020 в 6:56
  • @Ildar, спасибо, теперь понял! Что-то забыл, что можно воспользоваться разложением числа :) 1 июл 2020 в 8:50
0

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

# если число разложить в виде произведения простых чисел (например, 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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.