Ruby项目Euler＃12效率
研究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) 那个必需的文件（我试图把方法放在一堆Euler问题中）：
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）。 但是除了废除库素数解决方案并将所有素数添加到一个数组中我一直指的是 – 我觉得它只会使它更快一点 – 我想不出如何更快地做到这一点。 它需要更快。
我觉得这一切都错了吗？ 有什么建议？
同样有用的是如何提高我的任何库方法的效率，我可能会一次又一次地使用它。 我想从头开始制作它们，所以我理解它们，但我担心它们效率很低。
从你的代码：
这里的想法是2 ^ n是具有n个因子的最小数字
从所述的Project Euler任务：
我们可以看到28是第一个超过五个除数的三角形数。
我不确定为什么你认为2 ^ n是具有n个因子的最小数字，但问题中给出的例子清楚地certificate了你的假设是错误的，因为2 ^ 5 = 32，大于28。
我的解决方案从1开始搜索并且效率相当高。 我根本不使用素数。
附录：为了完整起见，另一个大问题，除了从一个太高的数字开始，正在搜索超过5000个除数而不是大于500，正如你在评论中注意到并指出的那样。