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