优化 Project Euler 12 (Python) 的解决方案

Question

我有以下针对 Project Euler Problem 12 的代码。但是，执行起来需要很长时间。有人有加快速度的建议吗？

n = input("Enter number: ")
def genfact(n):
    t = []
    for i in xrange(1, n+1):
        if n%i == 0:
            t.append(i)
    return t

print "Numbers of divisors: ", len(genfact(n))
print

m = input("Enter the number of triangle numbers to check: ")
print
for i in xrange (2, m+2):
    a = sum(xrange(i))
    b = len(genfact(a))
    if b > 500:
        print a

对于 n，我输入任意数字（例如 6）只是为了检查它是否确实返回因子数量列表的长度。对于 m，我输入 80 000 000

对于少量的情况，它的工作速度相对较快。如果我输入b > 50；对于 a，它返回 28，这是正确的。

Answer 1

我在这里的答案并不漂亮或优雅，它仍然是蛮力。但是，它稍微简化了问题空间，并在 10 秒内成功终止。

获取 n 的因子： 就像@usethedeathstar 提到的那样，可以测试最大为 的因子n/2。然而，我们可以通过仅测试 n 的平方根来做得更好：

let n = 36
=> factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1)

正如您所看到的，它在 6（36 的平方根）之后循环。我们也不需要显式返回因子，只需找出有多少个因子...所以只需使用 sum() 内部的生成器对它们进行计数即可：

import math

def get_factors(n):
    return sum(2 for i in range(1, round(math.sqrt(n)+1)) if not n % i)

测试三角形数

我使用生成器函数来生成三角形数：

def generate_triangles(limit):
    l = 1
    while l <= limit:
        yield sum(range(l + 1))
        l += 1

最后，开始测试：

def test_triangles():
    triangles = generate_triangles(100000)
    for i in triangles:
        if get_factors(i) > 499:
            return i

使用探查器运行此命令，不到 10 秒即可完成：

$ python3 -m cProfile euler12.py 

361986 function calls in 8.006 seconds

这里节省的最大时间是get_factors(n)仅测试 n 的平方根 - 这使得速度更快，并且通过不生成因子列表可以节省大量内存开销。

正如我所说，它仍然不太漂亮 - 我相信还有更优雅的解决方案。但是，它符合更快的要求:)