Lua - Calculating Primes from 1 to n

Question

I am very new to Lua and am simply learning it through the mentors on my robotics team. They challenged us with the problem to print all the primes under 444. My attempt at this was:

isPrime = true

for i = 2, math.floor(math.sqrt(444)) do
     for n = 2, i-1 do
           if i % n == 0 then
                isPrime = false
           end
      end
if isPrime == true then
      print(i)
end
end

However, the program is only spitting back 2 and 3. Where is my fault?

bames53 bames53 · Accepted Answer · 2014-10-03T00:52:57

The loop prints out a number if isPrime is true, but isPrime gets set to false when you check the value 4, and nothing ever sets it to true again.

Your program consists of an outer loop for each number you want to check, and an inner loop for checking that number.

That inner loop is designed such that for prime numbers it will not touch isPrime, and for composite numbers it will set isPrime to false. So for prime numbers the value of isPrime will be whatever it was set to before the inner loop began. Since you want isPrime to be true at the end for prime numbers, you should set isPrime to true just before the inner loop.

Once you do that your program still has a bug. Your algorithm is a little bit confused on where exactly sqrt(n) matters.

Some other advice:

Get used to using local variables, not globals. This will help avoid bugs where you accidentally reset variables that you don't intend to.

local isPrime = true

Use consistent indentation. It will help when anyone reads your code. In this case your if isPrime == true then print(i) end code is not indented enough.

You can skip the == true in an if condition: if isPrime then print(i) end.

There's a better algorithm for finding all the primes up to a certain value named the Sieve of Eratosthenes. Here's an implementation in Lua:

function sieve_of_eratosthenes(n)
  local is_prime = {}

  for i = 1, n do
    is_prime[i] = 1 ~= i
  end

  for i = 2, math.floor(math.sqrt(n)) do
    if is_prime[i] then
      for j = i*i, n, i do
        is_prime[j] = false
      end
    end
  end

  return is_prime
end

local primes = sieve_of_eratosthenes(444)

for key, value in pairs(primes) do
  if (value) then
    print(key)
  end
end

Lua - Calculating Primes from 1 to n

1 Answers