我参加了codewars网站的python挑战赛我遇到了以下挑战：
42的除数是：1，2，3，6，7，14，21，42。这些因子的平方是：1，4，9，36，49，196，4411764。除数的平方和是2500，等于50*50，平方！
给定两个整数m，n（1结果将是一个数组，每个子数组有两个元素，首先是平方因子为平方的数，然后是平方因子的和。
输出应为：
list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]
list_squared(250, 500) --> [[287, 84100]]
我编写了以下代码，其中包含两个附加功能：一个用于确定数字的所有因子，另一个用于检查数字是否为完全平方。
确定所有因素的函数：
def fact(m):
return [i for i in range(1,m+1) if m%i == 0]
函数检查一个数字是否为完全平方，如果不是完全平方，则返回0
def square_root(x):
ans = 0
while ans < x // 2 + 1:
ans = ans + 1
if ans*ans == x:
return ans
break;
return 0
计算所需结果的函数
def list_squared(m, n):
# your code
fac=[]
for i in range(m,n+1):
sq_sum = sum(list(map(lambda x: x**2,fact(i))))
if square_root(sq_sum) != 0:
fac.append([i,sq_sum])
return fac
这段代码给出了正确的结果，但是太长了。我能够通过所有的测试结果，但它花费了我大约6000毫秒。当我试图提交代码时，Web提交返回算法效率低，它花费了超过1200毫秒，这是最大的。
如果有人能提出一个更好的算法，我将不胜感激。
最佳答案
您的代码有几个优化，但最大的优化是当ans*ans大于x时停止这里：
def square_root(x):
ans = 0
while True:
ans += 1
sqans = ans*ans
if sqans == x:
return ans
elif sqans > x:
return 0
可以删除
while中的条件，因为现在对平方值进行测试。通过优化，我从8秒降到0.07秒。
但这仍然不令人满意一般来说，包含中断或返回条件的算法至少是
250, 500，即使可以节省时间，复杂性也太高。只需检查四舍五入平方根的平方，您就可以做得更好：
def square_root(x):
ans = int(x**0.5 + 0.5) # rounded just in case it goes below the actual value (float inaccuracy)
sqans = ans*ans
return 0 if sqans !=x else x
我将执行时间再除以2（由Optimized way to find if a number is a perfect square确认）
旁白（这并没有加速那么多，但值得一提）：
在
O(n)中不需要将map转换为list：sq_sum = sum(map(lambda x: x**2,fact(i)))
也可以避免循环到最大数。循环到最大数除以2，并将最大数添加到列表中是等效的。最大数/ 2以上不存在除数
def fact(m):
return [i for i in range(1,m//2+1) if m%i == 0] + [m]
最终编辑：由于
sum中使用了列表理解，因此速度仍然很慢。我可以通过使用生成器来大幅缩短时间，并在其外部添加fact：def sqfact(m):
return (i*i for i in range(1,m//2+1) if m%i == 0)
最后的代码，现在运行得太快了，我只有0秒。
def sqfact(m):
return (i*i for i in range(1,m//2+1) if m%i == 0)
def square_root(x):
ans = int(x**0.5 + 0.5)
return 0 if ans*ans !=x else x
def list_squared(m, n):
# your code
fac=[]
for i in range(m,n+1):
sq_sum = sum(sqfact(i)) + i*i # add i square outside
if square_root(sq_sum):
fac.append([i,sq_sum])
return fac