Как уменьшить время выполнения программы?

Question

[Артем Кондрацкий]

Здравствуйте, решаю пробный тур олимпиады по программированию. Отправляю решение задачи на проверку, смотрю, а система проверила и дала половину баллов из-за "Превышено ограничение по времени".

скрины проверки

код

n = int(input())
 
max_dividers = 0
number_of_max_dividers = 0
for i in range(1, n + 1):
    dividers = 0
    for j in range(1, i + 1):
        if i % j == 0:
            dividers += 1
 
    if dividers > max_dividers:
        max_dividers = dividers
        number_of_max_dividers = i
 
print(number_of_max_dividers)
print(max_dividers)

и на всякий случай

условия задачи

заранее спасибо.

Answer 1

[Andrey Dugin]

Модифицированное решето Эратосфена:

import numpy as np
from numba import njit

# С использованием numpy
def max_divisors_v1(n):
    divs = np.ones(n + 1, np.uint8)
    for step in range(2, n + 1):
        divs[step::step] += 1
    divs[0] = 0
    num = divs.argmax()
    return num, divs[num]

# Без numpy, чистый Python
def max_divisors_v2(n):
    divs = [1] * (n + 1)
    for step in range(2, n + 1):
        for index in range(step, n + 1, step):
            divs[index] += 1
    divs[0] = 0
    cnt = max(divs)
    num = divs.index(cnt)
    return num, cnt

# JIT-компиляция с декоратором @njit
max_divisors_v3 = njit(max_divisors_v2)

Вывод результата и тайминги выполнения:

Comments

[longclaps]

Ловко ты насобачился!

[Andrey Dugin]

longclaps, это всё из-за лени)

[Артем Кондрацкий]

решение верное, но походу у этой говно-платформы не установлен numpy! наверное, поэтому во всех тестах превышено время исполнения. Но все равно, спасибо.

[Andrey Dugin]

Артем Кондрацкий, модифицируйте код, чтобы работал без numpy. У меня даже быстрее работать стало.

[Andrey Dugin]

longclaps, зацени скорость с @njit

[longclaps]

Andrey Dugin, мне и вчера было лень, и сегодня - да только решение твоё неверное.
Смотри:
Вот 1. У него 1 положительный делитель: 1
Домножим его на 2 (итого 2) У него 2 положительных делителя: 1 и 2
Домножим его на 2 (итого 4) У него 3 положительных делителя: 1, 2 и 4
Домножим его на 3 (итого 12) У него 6 положительных делителей: 1, 2,3,4,6,12

[Andrey Dugin]

longclaps, мой код даёт верные ответы (последняя колонка):

[longclaps]

Andrey Dugin, а, пардоньте, я не прочухал. Ты там что-то про Эратосфена пел, да и потёр. Честный эратосфен у меня, а вот твой алгоритм, увы, квадратичный.

[Andrey Dugin]

longclaps, про Эратосфена я написал, что у меня модифицированный алгоритм: в ячейках расположены счётчики, а не булевы значения.

[longclaps]

Andrey Dugin, ой, что-то я совсем оботдыхался, вру напропалую. У нас одинаковой сложности реализации, твоя красивше.

[Andrey Dugin]

longclaps, там не квадратичность, т.к. ёмкость вложенного цикла стремительно падает за счёт возрастающего step. На диапазоне до n=10^7 (дальше не смотрел) график очень близок к линейному.

[Andrey Dugin]

longclaps,
Количество операций алгоритма (синим) по сравнению с линейный графиком (красный):

Снижение ёмкости вложенного цикла:

В деталях для n=100: