Есть ли способ сделать этот код более эффективным?

Question

Мне нужно написать код для вычисления количества элементов, у которых есть максимальное количество делителей между любыми двумя заданными числами (A [0], A [1]) (включая оба). Я должен вводить данные в виде строки, разделенной пробелами. В первой строке входных данных указано количество случаев, представленных в примере. Этот код работает отлично, но для его выполнения требуется некоторое время. Может ли кто-нибудь помочь мне написать этот код более эффективно?

import numpy as np
from sys import stdin
t=input()
for i in range(int(t)):
    if int(t)<=100 and int(t)>=1:
        divisor=[]
        A=list(map(int,stdin.readline().split(' ')))
        def divisors(n):
            count=0   
            for k in range(1,int(n/2)+1):
                if n%k==0:
                    count+=1
            return count
        for j in np.arange(A[0],A[1]+1):
            divisor.append(divisors(j))
        print(divisor.count(max(divisor)))

Пример ввода:

2
2 9
1 10

Пример вывода:

3
4

Answer 1

Есть способ вычислить делители путем разложения числа на простые множители. Учитывая простое разложение, вычисление делителей происходит быстрее, чем пробное деление (которое вы делаете здесь).

Но разложение на простые множители должно быть быстрым. Для небольших чисел наличие предварительно рассчитанного списка простых чисел (легко сделать) может ускорить факторизацию простых чисел и быстрое вычисление делителей. Если вы знаете верхний предел проверяемых чисел (назовем его L), тогда вам понадобятся простые числа до sqrt(L). Учитывая простое разложение числа n = p_1^e_1 * p_2^e_2 * .. * p_k^e_k, количество делителей будет просто (1+e_1) * (1+e_2) * .. * (1+e_k)

Более того, вы можете предварительно вычислить и / или запомнить количество делителей некоторых чрезмерно используемых числа до некоторого предела. Это сэкономит много времени, но увеличит объем памяти, иначе вы можете рассчитать его напрямую (например, используя предыдущий метод).

Кроме того, вы можете немного оптимизировать код. Например, вы можете избежать постоянного преобразования int(t) (и тому подобного), сделать это один раз и сохранить в переменной.

Numpy можно вообще избежать, это лишнее, и я сомневаюсь, что добавляет любое преимущество в скорости зависит от этого.

Это должно сделать ваш код быстрее, но всегда нужно измерять производительность с помощью реальных тестов.