python - 优化有助于找到最大除数

Question

我正在尝试解决欧拉项目的问题 12。第一个有超过 500 个除数的三角形数的值是多少？（第 7 个三角形数为 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28）。这是我的代码，但速度不够快。。你有什么优化技巧吗？

n=0
a=0
list=[]
maxcount=0


while True:
    n+=1
    a+=n
    count=0
    for x in range(1,int(a+1)):
        if a%x==0:
            count+=1   
            if count>maxcount:
                maxcount=count
                print a, "has", maxcount, "dividors"

谢谢！

Answer 1

从这个实现非常快速素数分解的问题中获取代码：
快速素数分解模块

然后使用这个问题的答案将你的素数转换为所有除数的列表（长度就是你想要的）：
得到一个数字的所有除数的最佳方法是什么？

例如，您可以将以下函数（改编自第二个链接）从第一个链接添加到模块底部：

def alldivisors(n):
    factors = list(factorization(n).items())
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            if i >= nfactors:
                return
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1

然后在您的代码中计算您将使用的除数，len(list(alldivisors(a)))这将比您当前使用的蛮力方法更快地计算除数的数量。

Answer 2

从减少搜索空间开始，无需查看不是三角形数字的数字。也尝试查看除数range(1, sqrt(n))而不是range(1, n)

Answer 3

除了数论：尝试缓存，并以相反的方式做事。例如：当您已经知道 300 有 18 个除数（以及它们是什么）时，对于可被 300 整除的数字意味着什么？你能缓存这些信息吗？（你当然可以。）

纯 python 加速技巧对你没有帮助，你需要一个更好的算法。