我Python的Project Euler #12解法有何问题？

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

但是，当我把842161320这个数字输入到Project Euler的问题中时，它说这个答案不对。

我到底哪里做错了呢？

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

你计算的总因子数量不够准确。比如说，36这个数字有9个因子：1、2、3、4、6、9、12、18和36。虽然算法只需要测试比sqrt(n)小的数字来找到所有的因子，但你还是需要把那些隐含的“大”因子也算上。

Answer 3

我发现了两个问题：

• 你的 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

还有，使用 质因数来计算因子数量。你可以创建一个质因数缓存来提高性能。