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 in Questions 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:

Comments

  • 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

  • dave1707dave1707 Mod
    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

    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)

  • 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
    
  • dave1707dave1707 Mod
    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 :)

Sign In or Register to comment.