处理 Project Euler 的第 12 题：
三角形数的序列是通过添加自然数生成的。所以第 7 个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。前十项是：
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
让我们列出前七个三角形数的因数：
1:1 3：1,3 6：1,2,3,6 10：1,2,5,10 15：1,3,5,15 21: 1,3,7,21 28：1、2、4、7、14、28我们可以看到 28 是第一个有五个以上除数的三角形数。
第一个有超过 500 个除数的三角形数的值是多少？
这是我所拥有的：
require 'reusable'
# The idea here is that 2^n is the smallest number with n factors,
# according to their definition, so it's a good place to start.
# It also happens to be a HUGE number, so I'm worried I'm thinking
# about this wrong. Did 4999 instead of 5000, just to make sure
# I didn't overshoot.
start = 2 * 4999
# The faster way to calculate the nth Triangle number
def nthTriangle(n)
n * (n + 1) / 2
end
def answer(num)
i = startingTriangle(num)
while true
triangle = i*(i+1)/2
puts triangle
factors = numFactors(triangle)
return "#{triangle} is triangle number #{i}, with #{factors} factors." if factors > num
i += 1
end
end
# Basic reversal of the nthTriangle thing to figure
# out which n to start with in the answer function.
def startingTriangle(n)
power = n - 2
sqrt(power * 2).to_i - 1
end
puts answer(5000)
还有那个必需的文件（我试图将我将在一堆欧拉问题中重用的方法放入其中）：
def primesUpTo(n)
nums = [0, 0] + (2..n).to_a
(2..sqrt(n).to_i+1).each do |i|
if nums[i].nonzero?
(i**2..n).step(i) {|m| nums[m] = 0}
end
end
nums.find_all {|m| m.nonzero?}
end
def prime?(n)
test = primesUpTo(sqrt(n).to_i)
test.each do |i|
if n % i == 0
return false
end
end
true
end
# Just for faster, more intuitive (to me) array summing
def sum(array)
array.inject(0) {|s, n| s + n }
end
# Ditto
def product(array)
array.inject(1) {|p, n| p * n}
end
# I don't like typing the 'Math.'
def sqrt(n)
Math.sqrt(n)
end
# Returns an array of arrays of the prime factors of num
# Form [[factor1, power1],[factor2, power2]]
# Ex: primeFactors(12) == [[2,2],[3,1]]
def primeFactors(n)
array = []
# 2 3
primesUpTo((n/2).to_i+1).select{ |i| n % i == 0 }.each do |p|
pcount = 1
n = n / p
while n % p == 0
pcount += 1
n = n / p
end
array << [p, pcount]
end
array
end
# Returns the number of factors a number has
# INCLUDING both the number itself and 1
# ex: numFactors(28) = 6
def numFactors(n)
return 2 if prime?(n)
product = 1
primeFactors(n).each do |i|
product *= i[1] + 1
end
product
end
我的问题是我的代码真的超级慢。如果我从 1 而不是我的起始编号开始，则需要一分钟 + 才能达到 200000（远不及 2^4999）。但除了废弃库素数解决方案并将所有素数添加到我一直提到的数组中——我觉得这只会让它更快一点——我想不出如何让它更快。它需要更快。
我在想这一切都错了吗？有什么建议么？
关于如何提高我的任何库方法的效率的任何建议也很有用，我可能会一次又一次地使用这些方法。我想从头开始制作它们，所以我理解它们，但我担心它们效率很低。