(永远运行)找到超过500个因子的三角形#

Question

我目前正在研究peuler问题.我认为我有正确的代码,因为我用示例中提供的代码测试了它.但是,当我尝试运行它以找到超过500个因子的第一个三角形数字时,它会保持运行超过15分钟.但是当我尝试找到超过100个因子的第一个三角形数字时,它会在一分钟内找到它.

请看下面:

我的问题是我如何才能更快地计算出来？因为好像被卡住了？

#Project 12 #http://projecteuler.net/problem=12

def triangle(x) #finds the (x)st triangular number
    x=(1..x)
    return x.inject(:+)
end

def factors(x) #calculates how many factors (x) has
    factors =[]
    range=(1..x)
    range.each {|num|
    if x%num==0 
        factors << num
    end
    }
    return factors.length
    end 

def project12(x) #finds the first triangular number that has over (x) factors
i=1
    until factors(triangle(i)) > x
        i += 1
    end
return triangle(i)
end

print project12(500)

Answer 1

所以,在三角形(x)中,你做了x-1补充.您可以通过这种在运行i,并达到i在你的代码,所以我们有(i-1) + (1 + 2 + 3 + 4 + 5 + 6 + ... + i - 1) which approximates to i^2/2.然后,在您的代码基本上x按时运行的因素.你为每一个做到这一点triangle(i),所以我们有1*triangle(1) + 2*triangle(2) + 3*triangle(3) + 4*triangle(4) + ... + i*triangle(i) = 1*0 + 2*1 + 3*2 + 4*3 + ... + i*(i-1), which is approximately i^3/3 - i/3.

这是什么意思？这意味着根据我的草图,您的程序将在大约i^3/3 - i/3 + (i-1)迭代时运行.这是立方时间,绝对不会扩展.

例如,如果我们不得不这样做i = 50,那么这将持续41699次.现在,让我们想象一下这样做一次:44255次i = 51.这肯定不会扩大规模.