Need help, my code is running elsewhere but i get error


#1

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

Hi I need help, my code is running elsewhere but i get this error "Oops, try again. Your function fails on is_prime(2). It returns None when it should return True."t


Is_prime
Problem in one testcase.code works for rest others
#2

Try backing off the indentation so it lines up with for instead of if. What happens then?

It will fail on 2, though, so that will still need to be rectified. Actually I spoke too soon. It will pass on 2. What was I thinking?

2 True
3 True
4 False
5 True
6 False
7 True
8 False
9 False
10 False
11 True
12 False
13 True
14 False
15 False
16 False
17 True
18 False
19 True
20 False
21 False
22 False
23 True
24 False
25 False
26 False
27 False
28 False
29 True

Edit:

If Prime numbers are of interest to you, on top of coding, this might add to your insight...

One question always comes up once we have working code... Can we improve or simplify it? In this case, yes we can. Consider.

if x > 1:

    # code

else:
    return False

What if we change the condition and move the return statement up there?

if x < 2: return False

Now all the remaining code can be moved to the left one indent and be simpler already.

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

Are we done yet? No. We can still remove the other else.

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

Done yet? For the purposes of this exercise, which you passed with your own code, this is far enough. Otherwise, no, we can do more.

What should the range actually be? It for sure doesn't need to be more than one half of x (we would add 1 to the integer of x / 2). Nothing more than half (of itself) can divide into a number. So that gives us,

def is_prime(x):
    if x < 2: return False
    for i in range(2, int(x / 2 + 1)):
        if x % i == 0:
            return False
    return True

We can still dial down the range some more. Consider, 3 goes into 27, 9 times. So if we have one factor, we find the other. If x is 27 we won't even have to go up to 9 in our range, 6 will suffice. The square root of 27, rounded down to the closest integer, plus 1.

int(27 ** 0.5) + 1 => 5 + 1

We now have,

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

We can reduce the load furrther by taking strides from odd to odd in the range, and skip all the evens. Only difficulty is that we start on 2, the only even Prime. To remedy this, we explicitly jump around 2 and start on 3.

Now we can set our stride to 2 with no difficulty; except, now we have to iterate over even values for x which before we didn't, they were ejected on the first iteration. This means another explicit test to rule them out. With them gone and the range consisting of only odd numbers we can rifle through the iteration in no time.

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

That's about as far down as we can narrow without introducing a list of known Primes. For instance, 27 is divisible by the Prime, 3, so is not Prime. Even if we didn't divide by anything else, we would have our answer right there. The shortest list of factors are the Prime factors. Rule them out and you have a Prime.

@appylpye wrote a sieve somewhere (I'm pretty sure it is in Python) that can generate a truth table to check primes against. In the case of 27 would only need the first three primes. A short list, indeed. Basically we would take the integer square root of x, add 1 to account for rounding, use that as the upper limit on the sieve.To check the primeness of 1087 we only need the primes less than 33 (10 in all). Not very many for a sieve to generate. It would very likely take less time than iterating all the odds in the divisor list for a large number, even with having to generate the list. I'll leave this door open for you to explore.


#3

Below is a Python program that utilizes a sieve of Eratosthenes. Creating a long list of primes is not the most efficient approach to the current exercise, however a list of primes might be useful in other contexts.

# sieve_of_eratosthenes.py
# Sieve of Eratosthenes
def sieve(n):
    # Initialize the list of integers
    # Primes from 2 to n, inclusive, will be marked as True
    primes = [True for i in range(n + 1)]
    # Assume 0 and 1 are not prime
    primes[0] = False
    primes[1] = False
    # Sieve the list of integers
    for i in range(int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(2 * i, n + 1, i):
                primes[j] = False
    return primes

primes = sieve(100)
for n in range(len(primes)):
    if primes[n]:
        print(n)

See:

Last edited December 8, 2016


#4

To morph to the hybrid approach...

def is_prime(x):
    if x < 2: return False
    if x > 2:
        p = sieve(int(x ** 0.5 + 1))
        primes = [i for i in range(len(p)) if p[i]]
        for i in range(len(primes)):
            if x % primes[i] == 0:
                return False
    return True

Evenness is again up for discussion. The first prime is 2, so all evens are ejected on the first iteration. However, there is still the call to sieve() to consider. When testing a sequence, it will add to the laod significantly when one thinks about it. Might have to leave that precondition in place.

if x < 2 or x % 2 == 0: return False

The primes list is filtered out of the sieve's truth table with the indices going to the new list. Still blows me away how elegant the sieve is. Makes one wonder why we would iterate at all when we can just wind up the sieve to N and see what the Nth index holds. True, it's a Prime. But on the other hand, iteration helps with the heavy lifting in terms of memory usage (one supposes) and requires a much smaller truth table.

I'm no benchmark person, but I would be interested to know more about how each uses and or wastes resources.


#5

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