密码战。整数：娱乐一。我有错误“执行超时”

Question

我试着做代码战中的任务。在

42的除数是：1, 2, 3, 6, 7, 14, 21, 42。这些除数的平方是：1, 4, 9, 36, 49, 196, 441, 1764。平方除数的和是2500，它是50 * 50，一个平方！在

给定两个整数m, n (1 <= m <= n)，我们要找到m和{}之间的所有整数，它们的平方除数之和本身就是平方。42就是这样一个数字。在

结果将是一个数组，每个子数组有两个元素，首先是平方除数是平方的数，然后是平方除数的和。在

示例：

list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]

list_squared(42, 250) --> [[42, 2500], [246, 84100]]

以上是问题的指导老师。在

我的代码已经通过了所有测试，但是有一个错误Execution Timed Out，可能我的代码没有优化。也许有人帮我优化我的代码。在

这是我的密码

^{pr2}$

Answer 1

我们将任务分为两部分：计算除数平方和和和识别平方。在

对于任务的前半部分，来自数论领域的除数函数sigma(k,n)返回n的除数的第k次幂之和；如果k=0，则返回除数的计数：

def sigma(k, n):
  def add(s, p, m):
    if k == 0: return s*(m+1)
    s *= (p**(k*(m+1))-1)
    return s / (p**k-1)
  fs = factors(n)
  p,m,s = fs.pop(0),1,1
  while len(fs) > 0:
    f = fs.pop(0)
    if f <> p:
      s,p,m = add(s,p,m),f,1
    else: m += 1
  return add(s, p, m)

如果n很大，这比暴力列表理解计算除数，然后再平方和求和要快得多。如果n不是太大（约为10**12），用2,3,5素数轮进行试算是求n因子的一种简单算法：

^{pr2}$

因此，factors(42)返回[2,3,7]，而sigma(2,42)返回2500。如果你的n更大，你需要一个更好的因子分解算法。在

问题的另一半是识别正方形。您可以使用内置的sqrt函数，但它适用于浮点数，因此不精确，所以您可能需要更好的函数。Isaac Newton给出了一种用导数逐次逼近的方法计算整数平方根的算法：

def isqrt(n):
    x = n; y = (x + 1) // 2
    while y < x:
        x=y; y=(x+n//x)//2
    return x

此函数返回最大值x，其中x²≤n。为了识别平方，我们可以计算平方根并乘以以检查数字是否为平方，但计算平方根是昂贵的，因此在执行平方根计算之前过滤明显的非平方是值得的：

def isSquare(n):
  if 33751571 >> (n % 32) & 1 == 0 \
  or 38348435 >> (n % 27) & 1 == 0 \
  or 19483219 >> (n % 25) & 1 == 0 \
  or   199411 >> (n % 19) & 1 == 0 \
  or   107287 >> (n % 17) & 1 == 0 \
  or     5659 >> (n % 13) & 1 == 0 \
  or      571 >> (n % 11) & 1 == 0 \
  or       23 >> (n %  7) & 1 == 0 :
    return False
  s = isqrt(n)
  if s * s == n: return s
  return False

幻数是一组bloom过滤器，它们丢弃了不是二次剩余的数；在进行昂贵的平方根计算之前，它们总共识别出99.82%的非平方。通过以下程序计算大方坯过滤器：

def q(n):
from sets import Set
s, sum = Set(), 0
for x in xrange(0,n):
  t = pow(x,2,n)
  if t not in s:
    s.add(t)
    sum += pow(2,t)
return sum

因此，例如，q(32)=33751571，二次剩余（函数内部计算的集合s为0、1、4、9、16、17和25。只有7/32=21.875%的非平方数通过了测试。结合其他测试，只有0.18%的非平方数没有被一个过滤器捕捉到，所以对昂贵的平方根函数的大多数调用只是简单地确认数字是平方的。在

有了这些，就可以轻松地执行所需的任务：

def task(m,n):
  result = []
  for x in xrange(m,n):
    if x == 1:
      result.append([1,1])
    else:
      s = sigma(2,x)
      if isSquare(s):
        result.append([x,s])
  return result

注意，1需要特殊处理，因为1没有素数因子（既不是素数也不是复合因子）。对于m=1，n=250，我们得到：

>>> task(1,250)
[[1, 1], [42, 2500], [246,84100]]

多么有趣的任务啊！{6}需要一个足够聪明的编程（cd6）位过滤器。它在OEIS中显示为序列A046655，在projecteuler中显示为Problem 211。您可以在Ideone上运行该程序。在

顺便说一句，如果m和n之间的差异很大，您可以筛选出因子，而不是对每个数进行单独的因子分解。我给出了一个程序来筛选my blog处一个范围内的最小素数因子；您可以修改该程序以收集所有因子，而不是仅收集最小因子。在