Lua Prime Number Checker

Question

Here is my Lua code for taking user input, and checking if the number entered is prime. My issue is that the program thinks that any even number is not prime, and any odd number is.

 print("Enter a number.")
 local number = io.read("*n")

 function prime(n)
 for i = 2, n^(1/2) do
   if (n % i) == 0 then
     return false
   end
   return true
 end
 end

 if prime(number) == true then
   print("Your number is prime!")
 end

 if prime(number) == false then
   print("Your number is not prime!")
 end

Answer 1

Move return true out of the loop.

Hence:

function prime(n)
    for i = 2, n^(1/2) do
        if (n % i) == 0 then
            return false
        end
    end
    return true
end

Answer 2

You return true too soon. You return true as soon as any i meets the condition. You must place the return after the loop.

Answer 3

I know it's an old post but since it's near the top on google I figured it can't hurt to post up my prime finder. It basically does a few simple checks of the obvious stuff and then loops through whats left in a similar fashion to the first example in Jon Ericson' post. Haven't benchmarked it but it seems to cope well enough.

--returns true if prime
function isPrime(n)
    local n = tonumber(n)
    --catch nil, 0, 1, negative and non int numbers
    if not n or n<2 or (n % 1 ~=0) then 
        return false
    --catch even number above 2
    elseif n>2 and (n % 2 == 0) then 
        return false
    --primes over 5 end in 1,3,7 or 9
    --catch numbers that end in 5 or 0 (multiples of 5)
    elseif n>5 and (n % 5 ==0) then 
        return false
    --now check for prime
    else
        --only do the odds
        for i = 3, math.sqrt(n), 2 do
            --did it divide evenly
            if (n % i == 0) then
                return false
            end
        end
        --can defeat optimus
        return true
    end
end

Answer 4

If you are going to be checking primality, you might as well pick an efficient algorithm. As one answer (cryptically) pointed out, all even numbers greater than 2 are not prime. Therefore, you can short-circuit the check for half the numbers, which doubles the speed to check any particular number:

function check_prime (x) 

  -- Negative numbers, 0 and 1 are not prime.
  if x < 2 then 
     return false
  end

  -- Primality for even numbers is easy.
  if x == 2 then
     return 2
  end
  if x%2 == 0 then
     return false
  end

  -- Since we have already considered the even numbers,
  -- see if the odd numbers are factors.
  for i = 3, math.sqrt(x), 2 do 
      if x%i == 0 then 
         return false
      end 
  end 
  return x 
end

There are all sorts of optimizations we could apply, but let's take a shot at doing this in a more Lua manner:

function sieve (x)
  if x < 2 then 
     return false
  end

  -- Assume all numbers are prime until proven not-prime.
  local prime = {}
  prime[1] = false
  for i = 2, x do 
      prime[i] = true 
  end 

  -- For each prime we find, mark all multiples as not-prime.
  for i = 2, math.sqrt(x) do
      if prime[i] then
         for j = i*i, x, i do
             prime[j] = false
         end
      end
  end

  return prime
end

To use the sieve function:

prime = sieve(number)
if prime[number] then
   print("Your number is prime!")
else
   print("Your number is not prime!")
end

In my tests, the sieve version is about 6 times faster than the previous algorithm for generating all the primes less than 1 million. (Your mileage may vary.) You can easily check the primality of all numbers less than number at no extra cost. On the other hand, it uses more memory and if you really want check the primality of just one number, it's less efficient.

Answer 5

I would check for primes by dividing the number with 2 and checking if the floor of the division is equal to the division. It looks like this.

if (input/2 == math.floor(input/2)) then
  print("is prime")
else
  print("is not prime")
end