CodeWars Python3.6代码的优化:整数:重新定义一个
我需要帮助优化我的python3.6代码的CodeWars整数:娱乐一个卡塔。
我们得到了一系列的数字，我们必须返回除数和除数之和，这是一个平方本身。
“42的除数是: 1，2，3，6，7，14，21，42。这些除数的平方是: 1，4，9，36，49,196,441,1764。平方除数之和是2500，等于50 * 50，a平方！
给定两个整数m，n (1 <= m <= n)，我们要找到m与n之间的所有整数，其平方除数之和本身就是正方形。42是这样一个数字。“
我的代码适用于单个测试，但在提交时超时：
def list_squared(m, n):
sqsq = []
for i in range(m, n):
divisors = [j**2 for j in range(1, i+1) if i % j == 0]
sq_divs = sum(divisors)
sq = sq_divs ** (1/2)
if int(sq) ** 2 == sq_divs:
sqsq.append([i, sq_divs])
return sqsq回答 2
Stack Overflow用户
发布于 2020-05-31 03:53:15
通过将最大范围设置为O(N)而不是num，可以降低从sqrt(num)+1到O(Log((N))的列表理解循环的复杂性。
通过从1到sqrt( num )+1的循环，我们可以得出这样的结论:如果I(循环中的当前项)是num的一个因子，那么num除以i必须是另一个因子。
例:2是10的倍数，5 (10/2)也是。
以下代码通过了所有测试：
import math
def list_squared(m, n):
result = []
for num in range(m, n + 1):
divisors = set()
for i in range(1, int(math.sqrt(num)+1)):
if num % i == 0:
divisors.add(i**2)
divisors.add(int(num/i)**2)
total = sum(divisors)
sr = math.sqrt(total)
if sr - math.floor(sr) == 0:
result.append([num, total])
return resultStack Overflow用户
发布于 2019-01-31 08:22:13
更多的是数学问题。i的两个最大除数是i本身和i/2。因此，您可以两次加速代码，只需使用i // 2 + 1作为范围停止，而不是使用i + 1。不过，别忘了增加i ** 2的i ** 2。不包括sq变量和sq_divs ** (1/2)，您可能希望得到一些微小的性能改进。
顺便说一下，您应该在第一个范围内使用n+1 stop。
def list_squared(m, n):
sqsq = []
for i in range(m, n+1):
divisors = [j * j for j in range(1, i // 2 + 1 #speed up twice
) if i % j == 0]
sq_divs = sum(divisors)
sq_divs += i * i #add i as divisor
if ((sq_divs) ** 0.5) % 1 == 0: #tiny speed up here
sqsq.append([i, sq_divs])
return sqsqUPD:我试过Kata了，现在还在超时。所以我们需要更多的数学！如果i可以被j除以，那么它也可以被i/j除以，所以我们可以使用sqrt(i) (int(math.sqrt(i)) + 1))作为范围停止。然后，if i % j == 0将j * j附加到除数数组中。然后if i / j != j追加(i / j) ** 2。
https://stackoverflow.com/questions/53826181
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号