我的python解决方案有什么问题吗？

Question

可能的扰流板警告

为什么我花了很多时间去改进算法，但是我不能解决这个问题。在

我试图解Project Euler #12，求出最小的三角形数有500个以上的除数，但它说我的答案是不正确的。在

下面是我的Python代码：

import time

# function to get the number of divisors
def div(n):
    d=2
    for i in range(2,int(n**.5)+2):
        if (n % i) == 0:
            d += 1
    return d

start = time.time()

w = True
n=m=1
while w:
    n += 1
    s = (n*(n+1))/2 # nth triangle number
    r = div(s)
    if r > m:
        m = r
        print s,"has",r,"divisors"
        if r > 500:
            w = False

print "Solved in",((time.time()-start)*1000),"milliseconds"

该代码的输出是（66秒后）：

^{pr2}$

。。。在

76576500 has 289 divisors
103672800 has 325 divisors
236215980 has 385 divisors
842161320 has 513 divisors
Solved in 65505.5799484 milliseconds

但是，如果我在ProjectEuler问题中输入842161320，它会说它是不正确的。在

我做错什么了？在

Answer 1

已解决

在Niklas的帮助下，改变了我的div方法，我得到了答案。而且，现在只需要我以前算法所用时间的8%。在

算法现在如下所示：

import time
import itertools

def div(n):
    d=0
    for i in range(1,int(n**.5)+1):
        if (n % i) == 0:
            d += 1
    return 2*d

start = time.time()

s = m = 0
for i in itertools.count(1):
    s += i
    r = div(s)
    if r > m:
        m = r
        print s,"has",r,"factors"
        if div(s) > 500:
            break

print "Solved in",((time.time()-start)*1000),"milliseconds"

Answer 2

我看到两个虫子：

• 您的div函数已损坏：div(24) == 5，而它应该是8
• 你的第一个三角形数字应该是3，尽管它应该是1

您可以如下实现工作div：

import math
def divisors(n):
  return sum(1 for x in range(1, n+1) if n % x == 0)

另外，该代码的效率非常低，一些改进建议如下：

不要使用公式计算第n个三角形数，而是使用滚动和：

^{pr2}$

另外，使用prime factors to calculate the number of divisors。您可以创建一个主因子缓存以获得最高性能。在

Answer 3

你低估了除数的总数。例如，36有9个除数：1,2,3,4,6,9,12,18,36。的确，该算法只需要测试小于sqrt(n)的数就可以找到所有的除数，但是您仍然需要在计数中包含隐含的“大”除数。在