Ruby 欧拉项目 #12 效率

Question

我正在尝试解决项目 euler 的问题 #12（请参阅下面的引用）

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

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 是第一个有超过五个除数。第一个有超过五百个因数的三角数是多少？

我已经写出了我 "think" 在 Ruby 中的有效解决方案，但是运行时间非常慢。请参阅下面的代码：

    def num_divisors_of(num)
  sum = 0
  for i in 1..num/2 do
    if num % i == 0 then sum += 1 end
  end
  return sum += 1
end

currentSum = 0

for i in 1..10000 do
  currentSum += i
   if num_divisors_of(currentSum) > 500
     puts currentSum
   break
   end
end

基本上，我从 1 开始，将其加到运行总数中，然后检查该总数的除数。如果人数超过 500，我将停止并 return 人数。

我想知道是否有另一种我还没有想到的方式来看待这个问题？我想过寻找质因数（我很确定我找到一个数字的除数数量的方法让我陷入困境），但除此之外我真的不知道在哪里可以提高效率。

有thoughts/ideas吗？

编辑：好的，我找到了一种节省运行时间的方法。在搜索除数时，我一直查找到数字的平方根，每次找到一个除数时加 2（例如：对于 625 的除数，我找到 5。5 * 125 = 625，所以这些是 2 个除数).接下来，如果平方根是一个精确的除数，则删除 1（因为我会计算两次。例如，25 * 25 = 625，但那只是 1 个除数）。

真的加快了我的运行时间，我得到了答案。哇哦！

Answer 1

看看这个答案： All factors of a given number

然后您只需计算数组中元素的数量，直到找到一个除数超过 500 的数组。

Ruby 欧拉项目 #12 效率

Ruby project Euler #12 efficiency

ruby

performance

optimization

runtime