我可以更有效地搜索具有 >500 除数的第一个三角形数吗？为什么我当前的实施速度很慢？

Question

我正在研究欧拉项目问题 12

第一个三角形数有超过五百个除数的值是多少？

我确信它可以为较小的数字产生正确的答案。例如，如果我将> 500替换为== 6，则得到的输出结果是预期的28。

对于 500 个除数，在执行大约两分钟后，程序开始运行非常缓慢。我相信这里的每个变量在每次迭代时都会被覆盖。 为什么很慢？ 我尝试将函数分离为函数以使用局部变量，但这并没有改善运行时间。

法典：

import sys
currentNumber, currentCalculationNumber, divisorCount, naturalNumber = 1, 1, 0, 1
while True:
while currentCalculationNumber <= currentNumber:
if currentNumber % currentCalculationNumber == 0:
divisorCount += 1
currentCalculationNumber += 1
if divisorCount > 500:
print ("ANSWER: " , currentNumber)
sys.exit(0)
naturalNumber += 1
currentNumber += naturalNumber
currentCalculationNumber, divisorCount = 1, 0

Answer 1

缓慢来自计算除数的蛮力方法。 解决方案的量级为 10^8，因此您以 10^16 次的量级遍历内部while循环：嵌套循环形成O(n(进程。 这需要一段时间。 你需要更有效的东西，至少是O(n log(n( (。

欧拉计划的目的之一是让我们研究更有效的算法。 对于这个，你可能想要使用除数函数，这将需要众多素数生成函数中的任何一个。

你应该开发一个"技巧包"模块，你可以为大多数问题import。 事实上，你应该已经有一个从早期问题中生成素数的(假设你正在按某种顺序攻击它们(。 如果没有，请尝试此。

Answer 2

我同意@Prune的回答，但这是您的蛮力算法的更快版本：

版本 1(较慢，使用 numpy 的蛮力攻击(

import numpy as np
i = 1
f = lambda N: (N * (N + 1)) // 2
ndmax = 0
while True:
t = f(i)
p = np.arange(1, t + 1)
r = np.mod(t, p)
nd = p.size - np.count_nonzero(r) + 1
if nd > ndmax: # track progress
ndmax = nd
print((i, t, nd))
if nd > 500:
print ("ANSWER: " , t)
break
i += 1

版本 2(快速，使用 sympy 的divisor_count(

from sympy import divisor_count
import numpy as np
i = 1
f = lambda N: (N * (N + 1)) // 2
ndmax = 0
while True:
t = f(i)
nd = divisor_count(t)
if nd > ndmax: # track progress
ndmax = nd
print((i, t, nd))
if nd > 500:
print ("ANSWER: " , t)
break
i += 1

有关更多详细信息，请参阅其中的divisor_count和参考。