如何解决 Lua 中的 Euler #12 项目？

Question

好的，这是另一个欧拉问题。我已经开始通过解决 Euler 项目问题来学习 Lua 并卡在 Euler problem 12.

在我看来很简单，我不明白为什么我的结果不正确？到目前为止，这是我的解决方案：

-- return triangular number of the specified number
function get_tri_num(num)
  local n = 0
  for i=1, num do
    n = n + i
  end
  return n
end

-- return all factors of the specifeid number
function factors(num)
  local factors = {}
  for i=1, num/2 do
    if num%i == 0 then
      factors[#factors+1] = i
    end
  end
  factors[#factors+1] = num
  return factors
end

-- get the first triangle number with >500 divisors
function euler12()
  local n = 0
  local trinum = 1
  while true do
    n = n + 7
    trinum = get_tri_num(n)
    if #factors(trinum) > 500 then break end
  end
  print(trinum, n)
end

euler12()

这个问题是计算密集型的，好吧，至少我是这样解决的，所以我使用 luajit.

time luajit euler12.lua 
103672800   14399

real    3m14.971s
user    3m15.033s
sys 0m0.000s

首先，我在问题描述中提供的玩具示例上尝试此解决方案。将 euler12() 行更改为 if #factors(trinum) > 5 then break end，我得到：

28  7

这对应于问题示例中显示的结果。

其次，在我看到玩具示例正常工作后，我运行 euler12() 和 >500 条件。根据我的解决方案，答案是 103672800 是的，如果我单独检查此结果的除数数 >500:

print(#factors(103672800))
648

但是...

Answer 1

问题出在这里：

while true do
  n = n + 7

为什么n每次都递增7？没道理，改成1，就可以得到正确答案了

但是，性能还是很差。几个可以改进的地方：

每次调用函数get_tri_num时，它都在计算从头开始，没必要。
你不需要一个数的因数，你只需要一个数的因子，那么为什么 return a table in factors?
for i=1, num/2 do 没有必要。迭代到的平方根 num足以得到因子数

同样的问题参考my code

如何解决 Lua 中的 Euler #12 项目？

How to solve project Euler #12 in Lua?

lua

factors