python - 为什么我的代码很慢(它还能工作吗)？ [欧拉计划 12][Python 3.3]

Question

我为 Project Euler #12 编写了这段代码。它非常慢(或者不起作用)，我发现了另一个非常相似的代码，并立即得到答案。 我的代码:

import math

def get_triangular(nth):
    return sum(range(1,nth+1))

def get_divisors_count(n):
    divisors = 0
    for a in range(1,math.ceil(n/2)+1):
        if n%a == 0:
            divisors += 1
    return divisors

a = 1
while(True):
    if get_divisors_count(get_triangular(a)) > 500:
        print(a)
    a += 1

我在 Stack Overflow 上找到的代码:

import math

def main():
    l = []
    one = 0
    a = 1
    b = 2
    while one == 0:
        a = a + b 
        b += 1
        l = []

        sqrt_a = int(math.sqrt(a))

        for x in range(1, sqrt_a + 1):
            if a % x == 0:
                l.append(x)
                if x < math.sqrt(a):
                    l.append(a // x)
                if len(l) > 500:
                    # print(a)
                    one = 1

    print(a, b, len(l))

if __name__ == '__main__':
    main()

Answer 1

首先，你的程序永远不会结束。您有一个 while True 循环，没有 break 或任何其他方式退出循环。您发布的其他代码具有 while one == 0 而不是 while True，并且只要 len 就设置 one = 1 (l) > 500。这有点尴尬，但确实有效。

所以:

a = 1
while(True):
    if get_divisors_count(get_triangular(a)) > 500:
        print(a)
        break
    a += 1

这仍然相当慢，但不是无限慢。

---

下一个最大的区别是，您计数到 n/2+1，而其他代码计数到 sqrt(n)，并将每个除数计数两次。 (为什么这个有效？想一想:如果 a 是 n 的除数，那么 n/a 也是，并且恰好是以下之一它们必须小于 sqrt(n) 除非它们都等于它。)

---

您还在其他程序没有浪费的一些地方浪费了一些时间，例如一遍又一遍地计算 sum(range(1, nth+1))，而不是保持运行总和并执行 running_sum += a。另一方面，通过仅保留除数的计数而不是构建除数列表然后计算其长度，您已经节省了一些时间。

但与之前的问题相比，这些都是次要的。至少您的程序现在具有相同的算法复杂度，O(N**1.5)，而不是 O(N**2)(或无限)；在我的机器上，它的运行时间为 15.3 秒，而 12.1 秒。

如果您确实想让速度更快，有两个主要选择:

1. 从数学角度看一下，看看是否有比暴力破解更好的方法来解决这个问题。 (提示:可以看出质因数分解对你有什么帮助吗？)
2. 弄清楚是否有可以记住(缓存)的信息，这会有所帮助。例如，如果你想计算 96 的因数，而你已经有了 24 的因数，这对你有什么好处吗？如果只有因子数怎么办？还是只有质因数？