Is_prime problem


#1



https://www.codecademy.com/courses/python-intermediate-en-rCQKw/0/6?curriculum_id=4f89dab3d788890003000096#


Error: Oops, try again. Your function fails on is_prime(4). It returns True when it should return False.


Guys, help me. I don't understand my mistake, tried everything I could and this error is the best result.


x = raw_input
    
def is_prime(x):
    if x <= 1:
        return False
    elif x == 2:
        return True
    elif x >= 3:
        for n in range(2, x):
            if x % n != 0:
                return True


#2

Lets put an input x = 4..

we see that if's condition turns out to be False and does not run the inside code.
Thus the function returns None (as it has nothing to return)

Instead of..

if x % n != 0:
                return True

We can do this..

if x % n == 0:
                return False

also you need to add an else statement so if a number greater than or equal to 3 is prime then it should return True,

update** @websolver15348


#3

No else required. That just complicates things.


#4

Wow! Yeah,only last return statement would be suffice !


#6

OK, now the function fails on is_prime(9) :smiley:

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

#7

You dont need raw_input ..

if x % n == 0:
    return False
else:
    return True

no need to use else..
Just return True? ..at the end of function ?


#8

Two states return False. Less than 2; and, is divisible by other than 1 or itself.

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

Notice that there is no complicated logic or testing of any values except as above. The number 2 will not be evaluated in the loop since it is not in the range. It will fall to the last line, as will the numbers that are not divisible in the loop.


#9

It was so easy! Thank you


#10

What we have here is a deterministic approach (brute force) that doesn't seek any efficiency, but goes through the entire range before letting a value pass. For large values of x this will get progressively slower.

We can make it more efficient in a number of ways, mostly in setting the range. The first approach would be to consider that any value larger than half of a number is not divisible into that number, so we can divide the range in half, right off the top. It will still be deterministic, though, just less iterations.

Getting more into factoring theory, we also know that the square root of a number is the largest factor we need to seek, since the opposite factor can be determined through normal division.

27 % 3 == 0
27 / 3 == 9

In this sense, we reduce the field to only those numbers between 2 and the square root of x. Again, way fewer iterations.

Is 25 prime?

25 % 2
25 % 3
25 % 4
25 % 5

Only four iterations to show that it is not. Notice that 5 is the square root of 25.

The final improvement on this approach would be to iterate only a list of odd numbers since no even numbers besides 2 are prime. Once we factor out two, we can step in two;s from 3 onward. It requires a reworking of the above example, but not by too much. Give it a try when you are up for the practice.

I left out one profound improvement... A list of primes only. This is indeed the fewest number of iterations, but we need a list of primes to begin with, or have our function generate an appropriate list in each case. Again, more study and practice when you are looking for something to explore.


#11

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