6/15 is_prime


#1
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3:
        return True
    for n in range(2,x-1):
        if n ** 2 == x:
            return False
        elif x % n == 0:
            return False
        else:
            return True

I'm not sure where I went wrong, it says that it's failing on is_prime(9) so it must have slipped through my first condition which would check for square roots. My issue is that I cant see how.


#2

What does return do?
Is there any way to execute one iteration of the loop without returning?


#3

Return would give an answer back to the function. I'm not entirely sure what you mean by only executing one iteration of the loop without returning.


#4

What does a function do after having returned?


#5

It should give the function an answer and exit the function right?


#6

Yes, so if you are guaranteed to return on the first iteration, when does the second iteration happen?


#7

Provided that the first condition is true and a square is found, would you really need to iterate anymore? Hold on, would I need something to tell it to test the next number in the range I've defined?


#8

You have a loop.

That means you expect it to be able to iterate multiple times.
That means you need to be able to do one iteration, and then another.

But if doing one iteration exits the function, then you can't do a second iteration, because the function is no longer running.

You've got:

repeat this 5 times:
    never mind, stop repeating

#9

I think I know what to do. You're right, I crossed some wires in what I coded and what I assumed would happen.


#10

Yes, your mistake is in not keeping the idea of the program separate from its implementation.

When you have such a separate version, be it in your head, in comments or a separate text, then you can compare it to what your code does, either by reading the code or by running it with print statements in it.

You always need a version of the program that you fully understand, one that you can reason about, one that you can convince yourself of that it will lead to the desired result in all scenarios.

If you've only got the one version in code, then if you don't understand the code you're screwed, blindly hammering at it, hoping something will make it work. No guarantees of it being correct when it appears to be working, because there's no reasoning about why it would be correct.


#12
def is_prime(x):
    if x < 2:
        return False
    for n in range(2,x-1):
        if n ** 2 == x:
            return False
        elif x % n == 0:
            return False
    else:
        return True

Thanks for the advice. After spending a little time away and following the code line by line objectively without thought of what it was for all it took was swapping out just a couple of things. There are 3 conditions for failure, if the number being examined is less than 2 it's an automatic False. If it's greater than two a range of numbers is generated and each number is tested by squaring it to see if n is equal to x, if it is then it's failed the second test and is false. The final test looks at the remainder, if it's not zero at anytime between 2 and x-1 it's false. If it passes all three trials then the number is prime. It's compact, simple, and easy to follow. I like to take a little bit or pride in its brevity :grin:


#13

Mmh sorry to rain on your parade, that second condition is redundant, the third condition would trigger on the same case.

However, you can stop the loop after sqrt(x) since beyond that you'll be testing for factors that you would already have discovered up to sqrt(x)

For example, sqrt(100) is 10, and you wouldn't need to try to divide by 25 because 4 which is less than sqrt(100) already covered that.

The last else can be skipped as well.

You can go even further and only test divisors in increments of 6, that would require adding some code though.