Project Euler#12的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秒内):

3 has 2 divisors
6 has 4 divisors
36 has 6 divisors
120 has 9 divisors

...

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

但是,如果我在Project Euler问题中输入842161320,则说它不正确.

我究竟做错了什么？

Answer 1

我看到两个错误:

• 你的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使用您的公式计算三角形数字,而是使用滚动总和:

import itertools

s = 0
for i in itertools.count(1):
  s += i
  if div(s) > 500:
    print s
    break

另外,使用素因子来计算除数的数量.您可以创建质因子缓存以获得最佳性能.