ruby - （永远运行）找到一个包含超过 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

So, in triangle(x), you do x-1 additions. You run through this at i and up to i in your code, so we have (i-1) + (1 + 2 + 3 + 4 + 5 + 6 + ... + i - 1) which approximates to i^2/2. Then, in factors your code runs essentially at x time. You do this for every triangle(i), so we have 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.

What does this mean? It means that based on my sketch your program runs at approximately i^3/3 - i/3 + (i-1) iterations. This is cubic time and definitely does not scale.

If, for example we had to do this up until i = 50, this would run 41699 times through. Now, let us imagine doing it just one time more: 44255 times if i = 51. That's definitely not going to scale.