2

我为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()
4

1 回答 1

3

首先，您的程序永远不会结束。您有一个while True没有 a 的循环break，或任何其他退出循环的方式。您发布的其他代码已while one == 0代替while True，并且设置one = 1为len(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)（或无限）；在我的机器上，与 12.1 相比，它运行时间为 15.3 秒。

如果你真的想让它更快，有两个主要选择：

  1. 从数学上看它，看看是否有比蛮力更好的方法来解决这个问题。（提示：可以看到素数分解对您有什么帮助吗？）
  2. 弄清楚是否有可以帮助记忆的信息（缓存）。例如，如果你想计算 96 的因数，而你已经有了 24 的因数，那你有什么好处吗？如果您只有因子计数怎么办？还是只有主要因素？
于 2013-10-01T18:41:28.370 回答