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

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:

## Comments

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.

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

Any idea about it?

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

@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