<p>有几种方法可以改进代码。你知道吗</p>
<p>首先,这里有一个更紧凑的<code>dSum</code>版本,它非常接近您的代码。运算符通常比函数调用快,因此我使用<code>** .5</code>而不是调用<code>math.sqrt</code>。我使用条件表达式而不是<code>if...else</code>块来计算步长。我使用内置的<code>sum</code>函数而不是<code>for</code>循环来累加除数;此外,我还使用整数减法从总数中删除<code>n</code>,因为这比调用<code>set.remove</code>方法更有效。你知道吗</p>
<pre><code>def dSum(n):
lst = set()
for i in range(1, int(n ** .5) + 1, 2 if n % 2 else 1):
if n % i == 0:
lst.add(i)
lst.add(n // i)
return sum(lst) - n
</code></pre>
<p>但是,我们不需要在这里使用集合。我们可以在找到除数对时把它们加起来,如果我们小心不要把任何除数加两次的话。你知道吗</p>
<pre><code>def dSum(n):
total = 0
for i in range(1, int(n ** .5) + 1, 2 if n % 2 else 1):
if n % i == 0:
j = n // i
if i < j:
total += i + j
else:
if i == j:
total += i
break
return total - n
</code></pre>
<p>这会稍微快一点,并且使用更少的RAM,但会增加代码复杂性。然而,有一种更有效的方法来解决这个问题。你知道吗</p>
<p>与其单独寻找每个数字的除数(因此也就是除数和),不如使用筛选方法,找到所需范围内所有数字的除数。下面是一个简单的例子。你知道吗</p>
<pre><code>num = 28124
# Build a table of divisor sums.
table = [1] * num
for i in range(2, num):
for j in range(2 * i, num, i):
table[j] += i
# Collect abundant numbers
abnum = [i for i in range(2, num) if i < table[i]]
print(len(abnum), abnum[0], abnum[-1])
</code></pre>
<p><strong>输出</strong></p>
<pre><code>6965 12 28122
</code></pre>
<p>如果我们需要求一个非常大的<code>num</code>的除数和,一个好的方法是求每个数的素数幂因子,因为有一种有效的方法可以从素数幂因子分解计算除数和。然而,对于这么小的数字,节省的时间并不足以保证额外的代码复杂性。(但如果您好奇的话,我可以添加一些素数幂筛代码;对于查找所有数字的除数和<;28124,素数幂筛技术的速度大约是上述代码的两倍)。你知道吗</p>
<p>AChampion的答案展示了一种非常简洁的方法,可以找到不能写成两个丰富数之和的数之和。但是,它有点慢,主要是因为它在<code>abnum</code>中循环遍历所有丰富的数字对。这里有一个更快的方法。你知道吗</p>
<pre><code>def main():
num = 28124
# Build a table of divisor sums. table[0] should be 0, but we ignore it.
table = [1] * num
for i in range(2, num):
for j in range(2 * i, num, i):
table[j] += i
# Collect abundant numbers
abnum = [i for i in range(2, num) if i < table[i]]
del table
# Create a set for fast searching
abset = set(abnum)
print(len(abset), abnum[0], abnum[-1])
total = 0
for i in range(1, num):
# Search for pairs of abundant numbers j <= d: j + d == i
for j in abnum:
d = i - j
if d < j:
# No pairs were found
total += i
break
if d in abset:
break
print(total)
if __name__ == "__main__":
main()
</code></pre>
<p><strong>输出</strong></p>
<pre><code>6965 12 28122
4179871
</code></pre>
<p>这段代码在运行python3.6.0的32位单核2GHz旧机器上运行大约2.7秒。在Python2上,大约快了10%;我认为这是因为列表理解在Python2中开销较小(在当前范围内运行而不是创建新范围)。你知道吗</p>