function doesn't work properly after running a "for loop"

Hi everyone!

I’ve written a code that checks if an integer is a prime or not and returns true (for primes) and false (for non-primes). Here it is:

```function isItPrime(n)
if n==1 then ans=false
elseif n==2 then ans=true
else
for i=2,n-1 do
if n%i==0 then ans=false
end
end
end
if ans==nil then ans=true
end
return ans
end

```

Let me explain the process. Obviously n=1 is not prime and and n=2 is prime, so we introduce them initially (otherwise there'll be problem in forthcoming "for loop"). In the "for loop" the program divides n by all integers smaller than itself and greater than 1 and if it was divisible to at least one of them it would return "false" to "ans".
Up to here the program has struck out n if it is "non-prime" by setting the answer "false". If the answer is not "false" so n must be prime, Thus we return "true" to the answer if it was nil. This code worked properly for all integers I tried.

Now we want to print all primes between 1 and 100. So we continue as:

for i=1,100 do
if isItPrime(i) then
print(i)
end
end

```

But the problem is it only prints 2 and 3 and doesn't continue for larger primes.
And what looks more strange is that after running this loop, the function isItPrime() will not work properly any more!
i.e. the answer to isItPrime(59) is false now!!
If you code like below:

function isItPrime(n)
if n==1 then ans=false
elseif n==2 then ans=true
else
for i=2,n-1 do
if n%i==0 then ans=false
end
end
end
if ans==nil then ans=true
end
return ans
end

print(isItPrime(59))

for i=1,100 do
if isItPrime(i) then
print(i)
end
end

print(isItPrime(59))

```

You would get this:
~~~
true
2
3
false
~~~
i.e. After running the loop, the function isItPrime() doesn't work properly anymore! Strangely!!
Any idea what happend?!```

Your variable `ans` is global so holds its value between successive function calls. Make `ans` local to the function and it should work.

(Your algorithm is extremely inefficient, by the way.)

as @Andrew_Stacey said you could improve the eficiency(?) by, for example
not dividing by 6 as all multiples of 6 are multiples of 3 and you have already checked all those

@Parsa Here’s your code written a different way.

``````
function setup()
for i=1,100 do
if isItPrime(i) then
print(i)
end
end
end

function isItPrime(n)
if n==1 then
return false
else
for i=2,math.sqrt(n) do
if n%i==0 then
return false
end
end
return true
end
end

``````

@andrew_stacy thanks! the problem with variable ans solved.

@Coder I understand what you mean, by the way the most effecient way is to only divide n by it’s preceding prime numbers. I tried to do it by replacing function in itself (like what we do in algorithm of factorial [at least it’s simplest algorithm!]). Tried the code below but it crashed:

```function isItPrime(n)
local ans
if n==1 then ans=false
elseif n==2 then ans=true
else
for i=2,n-1 do
if isItPrime(i) then
if n%i==0 then ans=false
end
end
end
end
if ans==nil then ans=true
end
return ans
end

```

@dave1707 I don't understand why you limit the for loop between 2 and sqrt(n). You mean there could not be a prime factor of n greater than sqrt(n)?!!
I think it's not mathematically true as well as 10 has prime factors 2 and 5 while 5>sqrt(n)```

Just on that last point, while it is true that a number, say `n`, might have a prime factor greater than `sqrt(n)` then it is also true that if it does then it must have one less than `sqrt(n)`. So in a primality test, it is sufficient to look up to (and including) `sqrt(n)`.

The recursive method is even more inefficient. Let’s consider `isItPrime(n)`. To do this, we need to test for divisibility by numbers from 2 to `sqrt(n)` but before we test for divisibility by `k` then we need to test if `k` is prime. To do that, we need to see if it is divisible by 2 to `sqrt(k)`, but before we test each of those, we need to test if they are prime. And so on.

The problem is that you are testing lots of times if the same thing is prime. And your recursion is simply adding to that list. If you want to make your algorithm more efficient then you need to remember things that you’ve already done. So once you know that, say, `k` is prime then you should remember it and not compute it again. Likewise, once you know that `r` is composite, remember that as well.

For a single number, though, this saving isn’t all that relevant because it’s longer to check if `k` is prime than to check if `n` is divisible by `k`. But for a list of numbers then it is a big saving.

However, the single most efficient thing you can do to your algorithm is to terminate it when it knows the answer.

``````function isItPrime(n)
if n==1 then return false
elseif n==2 then return true
else
for i=2,n-1 do
if n%i==0 then return false
end
end
end
return true
end
``````

@Parsa Just an example of “for i=2,math.sqrt(n) do” and the number we’re trying is 36
then we only go to 6 ( sqrt36) . 2x18=36 3x12=36 4x9=36 6x6=36. There’s no point going higher than 6 because the calculations 9x4=36 12x3=36 18x2=36 are the same as what we already did but just reversed.

@andrew_stacey @dave1707
Yeah! I got the point about sqrt(n)! It was smart but I didn’t mentioned

I must try a new algorithm for listing primes that doesn’t waste time for rechecking pre-checked numbers.
By the way, thank you for all annotations