查找给定范围内的数字，这些数字的除数之和具有完全平方并返回它们与相关的平方

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)

查找给定范围内的数字，这些数字的除数之和具有完全平方并返回它们与相关的平方

Finding the numbers in a given range who have a perfect square for the sum of their divisors and returning them with the associated square

python

math

optimization

cpython

mathematical-optimization