6. is_prime -- why is my code wrong?


#1

ERROR MESSAGE:

Oops, try again. Your function fails on is_prime(0). It returns None when it should return False.

CODE:

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

Is_prime I'm stuck and confused
#2

How would we go about returning False when x is 0 or 1?

The if statement should not have an else branch. It returns True on the first iteration of the loop. The return statement indentation should be the same as for.


#3

Thanks @mtf, I've added an if clause to remedy this.

I've also adjusted my for statement -- however it still returns None. Can't seem to find a simple solution.

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

#4

Nevermind, I see what I did wrong

Corrected:

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

#5

You will find in fact that your earlier example is only missing a last line:

return True

as in,

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

#6

I don't understand '(x-1)' , if we set range(2,x),it will iterate 2 to x-1. So why do we need minus 1 more??
thank for your answer.


#7

The simple answer is because that is what is given in the instructions, if I recall. The discussion has come up as to whether the author meant the literal, or not. We know that range() excludes the upper bound. As a stop index that element isn't bound to the list. Is the author implying that we act upon that understanding and write,

for n in range(2, x):

We know that x will not be included in the range, and the loop runs correctly. Whatever the case may be, it is moot since there are a lot of iterations that needn't take place. As many as half of them, and more.

Consider the number line. Place A at zero, and B at a point to right of it some distance. Let's offset A by 2 (that means B gets offset, as well, for now). We now have an interval that may contain Primes having excluded 0 and 1. That 2 is the only Prime with even parity is simple to detect. Just exclude it from the iteration.

   if x > 2:
       # exclusive
   return True

Now consider which numbers in the interval divide into B. Can any be greater than B / 2 ? Answer: No.

So the range could be (2, x / 2),

range(2, int(1 + x / 2))    # since B is B + 2, the quotient is 1 greater.

But why stop there? Since numbers in the interval can be factors of other numbers in the interval which are factors of B (technically B - 2), then the range need not exceed the square root of x, or, int(x ** 0.5 + 1) for good measure in the event of there being an edge case..

for n in range(2, int(1 + x ** float(1/2))):

graph of x^0.5

Again, why stop here? Are not all non-Prime numbers the product of two or more Primes? What if we have a list of primes already cached? Given that the square root limit is established, we needn't iterate over a very large list to determine primeness of the candidate. Something to explore.

def is_prime(x):
    if x < 2 or x % 2 == 0 and x != 2: return False
    if x > 2:
        for i in range(3, int(x ** 0.5) + 1, 2):
            if x % i == 0: return False
    return True

def primes_to_n(n):
    if n < 2: return
    primes = [2]
    primes += [x for x in range(3, n+1, 2) if is_prime(x)]
    return primes

def is_p(n):
    if n < 2: return False
    if n > 2:
        for i in primes_to_n(int(n ** 0.5 + 1)):
            if n % i == 0: return False
    return True

#8

Thx for giving the right limit explanation. So actually we just need to examine from 2 until int(x/2),because the numbers which are bigger than x/2 are no need to test. More precisely the square root of x. I am still wondering of int(1+x/2). Does the 1 of (1 + x/2) means to carry set the float number?
And thx for your detailed answer.It's helpful.


#9

The 1 in the case of x / 2 is to mitigate that we have offset the interval by 2. In the regards to the square root, it is intended to catch edge cases.

We need to set an upper limit on our function. Do we want to test primes in the millions? The square root is in the thousands. In the trillions? The square root is in the millions. How big a list do we need in order to measure in this range is all we need to determine at the outset. Then crank out a list and use that for all future queries.

This looks like a job for a factory.


#10

After some muddling, here is a prime tester factory:

def factory(n):
    P = primes_to_n(int(n ** 0.5 + 1))
    def is_p(x):
        if x < 2: return False
        if x > 2:
            for i in P:
                if x % i == 0 and i != x: return False
        return True
    return is_p

We give the factory an upper limit for which to produce a list of primes then return a function with that list instantiated in its scope.

To create a function that can test primeness for numbers up to a million, we only need all the primes up to 1001. 1009 is Prime so we could set the limit to 1010.

Eg.

>>> primes_to_n(1010)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 
263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 
359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 
569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 
659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 
769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 
881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 
997, 1009]

this limits our function to a maximum 169 iterations. So our custom function could be,

primes_to_M = factory(1010)

This function has the above list built in and can test any number up to the square of 1009 (which is not prime) but minus one it might be. As it turns out, minus 14 is prime.

>>> primes_to_M(1018067)
True

Is_prime
#11

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