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

Question

我有以下欧拉计划问题 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 的平方根 - 这使得它更快，并且您通过不生成因子列表来节省大量内存开销。

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