2

如何在仍然使用 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)

**我试图通过将所有东西放在一个函数中来优化代码以减少函数调用的数量，但它仍然没有给我真正想要的速度。**

4

1 回答 1

2

这是一些纯 Python 代码，可以相当快地完成您想要的操作。这以多种方式提高速度。首先，它使用数学方法计算一个数的除数之和，仅使用该数的素数分解（不同素数的幂的乘积）。其次，它使用先前计算的素数列表来加速素数分解。所以这段代码有更长的代码并使用更多的内存但速度更快。第三，我使用 Python 的内置is_integer函数来加速完美正方形的检测。最后，我从代码中删除了错误检查以加快速度。这段代码的作用是直到大于素数列表中最后一个数的平方的素数。您在评论中说您需要多达一千的数字。我把它增加到一百万，只是为了确定，这需要168质数。（如果你确定你永远不需要超过 1000，你可以使用第一个11质数，直到31.）

我刚刚在我的代码上运行，计算和打印结果列表%timeit需要几毫秒的时间。一百万只需要几秒钟。你需要更快的东西吗？3.2610009.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)
于 2018-12-13T17:42:44.387 回答