6. is_prime


#1



I've written the code bellow for exercise 6, with the help of the hint.


However, it fails on prime(3), as it returns None instead of True.


Since 3 is the number following those already covered on the if and elif statements, I believe the error must be in the else. Would be great if you could take a look, thanks.


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


#2

Should not be in the if statement or the loop. The way to test for 2 is to exclude it from the loop:

if x < 2: return False
if x > 2:
    for n in range(2, x):
        if x % n == 0: return False
return True

Since 2 is excluded from the loop, if returns True. So too will the return be True if the loop completes without returning False.


#3

thnx a lot ,had the same problem P.S. no more


#4

I had the same problem and could settle it with your help! Thanks! But I can't understand why it works without "else"? Which If-statement does "return True"(in the end) belong to? Thanks beforehand!


#5

to understand why this works, you need to understand that a function ends the moment a return keyword is reached. So if the number is not a prime, False will be returned, the rest of the function is never executed

with other words, if the loop finishes, the number is a prime number, so you can immediately return True, it doesn't really belong to anything


#6

Thank you for your explanation! If the loop couldn't find a number(between 2 and x) that can divide x evenly, then it should return True(number is prime number). If there is a number(can divide x evenly), function ends and returns False.


#7

the return false causes the function to end, but yes, that is the essence of it :slight_smile:


#8

Like Steven says, it doesn't belong to anything but the function itself. What we've done is turn to a simple binary solution set. True or False, and foregone all other checks and tests. Two possible outcomes, two return statements.

Can we refine this code a bit more? Yes. We can make it more efficient by limiting the number of test cases. Take for instance the upper bound of the loop range. Does it need to be x or can work with a smaller number?

Answer: We have two choices of smaller numbers along two lines of reasoning:

  1. A number greater than half of another number cannot be a factor of that number. so int(x / 2) + 1 is a viable range. If we add 1 to that, then x / 2 is included in the range.

  2. The factors of a number have at least one corresponding factor in the range of 2 to the square root of x. Make this an integer and add 1 to ensure that the maximum is in the range. So, int(x ** 0.5) + 1

Eg. 3 * 9 == 27, but then so does 9 * 3. The commutative property allows us to multiply in any order. It follows that once we find 3, we will find 9 so we don't need to look for 9, just the 3.

Another refinement would be in the step value of the range. However we need to add more logic to make this work.

def is_prime(x):
    if x < 2: return False
    if x > 2:
        s = 2 if n > 2 else 1
        for n in range(2, int(x ** 0.5) + 1, s):
            if x % n == 0: return False
    return True

Now the program will iterate through only the odd numbers in the range, except 2. Since the first iteration cycle catches all even values for x anyways, there is no reason to iterate over them.


#9

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.