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

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.

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)

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.