CODEWITHSUNDEEP
luafactors
tastyminerals
tastyminerals

Reputation: 6548

How to solve project Euler #12 in Lua?

Ok, here it goes another Euler problem question. I've started to learn Lua by solving Euler project problems and got stuck on Euler problem 12.

It looks to me very straightforward and I don't understand why is my result incorrect? Here is my solution so far:

-- 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()

This problem is computation intensive, well, at least the way I am solving it, so I use luajit.

time luajit euler12.lua 
103672800   14399

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

First, I try this solution on the toy example provided in the problem description. Changing the line of euler12() to if #factors(trinum) > 5 then break end, I get:

28  7

Which corresponds to the results shown in the problem example.

Second, after I see that the toy example is working I run euler12() with >500 condition. According to my solution the answer is 103672800 and yes, if I separately check the number of divisors for this result is >500:

print(#factors(103672800))
648

But...

enter image description here

Upvotes: 0

Views: 276

Answers (1)

Yu Hao
Yu Hao

Reputation: 122453

The problem is here:

while true do
  n = n + 7

Why does n increaments 7 each time? That doesn't make sense, change it to 1, and you could get the correct answer.

However, the performance is still poor. Several places that could be improved:

  • Every time the function get_tri_num is called, it's calculating from scratch, that's not necessary.

  • You don't need the factors of a number, you only need the number of factors of a number, so why return a table in factors?

  • for i=1, num/2 do is not necessary. Iterating to the square root of num is enough to get the number of factors.

Refer to my code for the same problem.

Upvotes: 2

Related Questions