MrO*_*Sir 3 python algorithm python-3.x
我尝试从代码战中完成任务。
的除数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和n其平方除数的总和本身就是一个正方形。42是这样的数字。
结果将是一个数组数组，每个子数组有两个元素，首先是除数平方为平方的数字，然后是除数平方的和。
例子：
list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]
以上是题主。
我的代码已经通过了所有测试，但是有一个错误Execution Timed Out，可能是我的代码没有优化。也许有人帮我优化我的代码。
这是我的代码
import math
def list_squared(m, n):
number = 0
result = []
if m==1:
result.append([1,1])
else:
number = m
squared_list(number)
result += squared_list(number)
for i in range(m + 1, n + 1):
number = i
squared_list(number)
result += squared_list(number)
return result
def squared_list(number):
array, arrays = [], []
x = sum([i*i for i in range(1, number//2+1)if not number%i]) + number*number
if math.sqrt(x) % 1 == 0:
array.append(number)
array.append(x)
arrays.append(array)
return arrays
我们将任务分解为两部分：计算除数的平方和和识别平方。
对于任务的前半部分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因子的简单算法：
def factors(n):
wheel = [1,2,2,4,2,4,2,4,6,2,6]
w, f, fs = 0, 2, []
while f * f <= n:
while n % f == 0:
fs.append(f); n /= f
f, w = f + wheel[w], w + 1
if w == 11: w = 3
if n == 1: return fs
else: return fs + [n]
因此，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 ²≤ ñ。为了识别平方，我们可以计算平方根并乘以检查数字是否为平方，但计算平方根很昂贵，因此在执行平方根计算之前过滤掉明显的非平方是值得的：
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
幻数是一组布隆过滤器，它丢弃不是二次残差的数字；总的来说，他们在进行昂贵的平方根计算之前识别了 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]]
多么有趣的任务！它需要一点数论（sigma函数）和一些巧妙的编码（布隆过滤器）来创建一个足够快的程序。它在 OEIS 中显示为序列A046655，在 Project Euler中显示为问题 211。您可以在Ideone 上运行该程序。
顺便说一句，如果m和n之间的差异很大，那么您可以筛选以找到因子，而不是单独分解每个数字。我在我的博客上给出了一个程序来筛选一个数字范围内的最小素因数；您可以修改该程序以收集所有因素，而不仅仅是最小的因素。