Поиск чисел в заданном диапазоне, которые имеют идеальный квадрат для суммы их делителей, и возврат их с соответствующим квадратом

Question

Как я могу оптимизировать код для запуска за минимальное время, все еще используя реализацию CPython?

 def detdivisors(n):
     """This function tests if the sum of the divisors of a given 
     a number is a perfect square and returns the sum if it is, and 
     false if it is not"""
     import math
     divisors = []
     sum = 0
     for i in range(1,n+1):
         if n%i == 0:
             divisors.append(i)
     for i in range(0, len(divisors)):
         sum = sum + (divisors[i]**2)
     if (math.sqrt(sum)%1 == 0):
         return sum
     else:
         return False
 def list_squared(m, n):
     """This function runs for the previous function and returns a 
     list that has all the numbers that satisfy the condition and 
     their associated sums. """
     answers = []
     for i in range(m, n+1):
     ans = []
     if detdivisors(i) != False:
        ans.append(i)
        ans.append(detdivisors(i))
        answers.append(ans)
     return answers
 num = int(input("Enter the beginning: "))
 end = int(input("Enter the end: "))
 ans = list_squared(num,end)
 print(ans)

** Я пытаюсь оптимизировать код, помещая каждую вещь в одну функцию, чтобы уменьшить количество вызовов функций, но она все еще не дает мне ту скорость, которую я действительно хочу получить,**

Answer 1

Вот некоторый чистый Python-код, который делает то, что вы хотите довольно быстро.Это набирает скорость множественными способами.Во-первых, он использует математический способ для вычисления суммы делителей числа, используя только простое разложение (произведение степеней различных простых чисел) числа.Во-вторых, он использует предварительно вычисленный список простых чисел для ускорения простого разложения.Таким образом, этот код имеет более длинный код и использует больше памяти, но работает быстрее.В-третьих, я использовал встроенную в Python функцию is_integer, чтобы ускорить обнаружение идеальных квадратов.Наконец, я удалил проверку ошибок из своего кода, чтобы ускорить его.Этот код работает до простого числа, большего, чем квадрат последнего числа в простом списке.Вы сказали в комментарии, что вам нужно число до тысячи.Я увеличил это до одного миллиона, чтобы быть уверенным, и это занимает 168 простых чисел.(Если вы уверены, что вам никогда не понадобится превышать 1000, вы можете использовать первые 11 простые числа, вплоть до 31.)

Я только что набрал %timeit в своем коде, и этотребуется 3.26 миллисекунд для вычисления и печати результирующего списка до 1000.Это займет 9.05 секунд, чтобы сделать это за миллион.Вам нужно что-нибудь быстрее?

import math

primelist = [
      2,     3,     5,     7,    11,    13,    17,    19,    23,    29,
     31,    37,    41,    43,    47,    53,    59,    61,    67,    71,
     73,    79,    83,    89,    97,   101,   103,   107,   109,   113,
    127,   131,   137,   139,   149,   151,   157,   163,   167,   173,
    179,   181,   191,   193,   197,   199,   211,   223,   227,   229,
    233,   239,   241,   251,   257,   263,   269,   271,   277,   281,
    283,   293,   307,   311,   313,   317,   331,   337,   347,   349,
    353,   359,   367,   373,   379,   383,   389,   397,   401,   409,
    419,   421,   431,   433,   439,   443,   449,   457,   461,   463,
    467,   479,   487,   491,   499,   503,   509,   521,   523,   541,
    547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
    607,   613,   617,   619,   631,   641,   643,   647,   653,   659,
    661,   673,   677,   683,   691,   701,   709,   719,   727,   733,
    739,   743,   751,   757,   761,   769,   773,   787,   797,   809,
    811,   821,   823,   827,   829,   839,   853,   857,   859,   863,
    877,   881,   883,   887,   907,   911,   919,   929,   937,   941,
    947,   953,   967,   971,   977,   983,   991,   997]

def sumdivisors(n):
    """Return the sum of the positive divisors of n. This is guaranteed
    to work if 0 < n < 1000000 and will work for many larger numbers.
    """
    sqrtn = int(math.sqrt(n))
    result = 1
    for p in primelist:
        if p > sqrtn:
            break
        exponentofp = 0
        while n % p == 0:
            n //= p
            exponentofp += 1
        if exponentofp:
            sqrtn = int(math.sqrt(n))
            result *= (p**(exponentofp + 1) - 1) // (p - 1)
    if n > 1:
        result *= n + 1
    return result

num = int(input("Enter the beginning: "))
end = int(input("Enter the end: "))
ans = [n for n in range(num, end+1) if math.sqrt(sumdivisors(n)).is_integer()]
print(ans)