#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

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

edited May 2014 Posts: 3

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?!

Tagged:

• Posts: 2,161

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

• Posts: 425

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

• Posts: 8,505

@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

``````
• edited May 2014 Posts: 3

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

• Posts: 2,161

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)`.

• Posts: 2,161

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
``````
• Posts: 8,505

@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.

• edited May 2014 Posts: 3

@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 