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