# is_prime 6:15 Why my program is not working?

#1

Hello, everybody
Plz, help

What's wrong with this code?
is_prime(9) returns true, but 9 % 3 == 0

``````n = int(raw_input("Input a positive integer: "))

def is_prime(x):
if x < 2:
return False

elif x == 2:
return True
else:
for i in range(2, x):
if (x % i) == 0:
return False
break
else:
return True
print is_prime(n)``````

#2
``````for i in range(2, x):
if (x % i) == 0:
return False
break
else:
return True``````

If the loop finishes without returning False, then return True at that time, not in an else statement before the loop completes.

``````else:
for ...
if ...
return False
return True``````

#3

Thank you for answer!
This code works

``````n = int(raw_input("Input a positive integer: "))

def is_prime(x):
if x < 2:
return False

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

return True

print is_prime(n)``````

#4

``````def is_prime(x):
if x < 2:
return False

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

return True``````

Technically, we don't need an `elif` since the we're dealing with fall-through more than multiway branching.

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

At this point we can abandon `if`. We've just rid ourselves of all the even numbers, returning 2 as True and the rest as False. We can reduce the sample by a huge factor with two lines:

``from math import sqrt``

at the top of the code; and,

``    r = int(sqrt(x)) + 1``

Now we can zip through the validation loop in a fraction of the time it would take to test all the values.

``````    flag = True
for n in range(3, r, 2):
if x % n == 0:
flag = False
break
return flag``````

#5

Explain, please

Why r = int(sqrt(x)) + 1 ?

#6

It relates to factoring. A number that is not prime can be factored. When looking at only two factors, we see the cross-over point at the square root. Never can both factors be greater than the square root. This means we can narrow the list to numbers between 2 (which we've excluded above) and the square root.

Not all numbers have an integral square root (perfect square). When we convert most roots to an integer, we make the number smaller. By adding 1 to the number, we make sure to test all possible factors.

Eg. Take 100, for instance.

`````` 2 * 50
4 * 25
5 * 20
10 * 10  <<< cross-over
20 * 5
25 * 4
50 * 2``````

#7

Very lucidly, thank you