[Solved] Trying to find the prime numbers using Python

The problem is that the return true should not happen until the for loop has completed.

what we have in the original code is a cuple of tests for trivial cases (x less than 3)
and then a loop for testing all the larger numbers.

In the loop an attempt is made to divide x by a smaller number (starting with 2) and then if it divides evenly False is returned, if it does not True is returned, that is the mistake, instead of returning true, the loop should be allowed to repeat, and division should be tried again with the next number, and only after the supply of divisors (from the for loop) has been exhausted should true be returned.

here’s a fixed version:

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

        return True

Others have commented that the loop need not continue all the way up to x and that stopping at sqrt(x) is sufficient, they are correct. doing that will make it faster in almost all cases.

Another speed up can be had if you have a list of small primes (upto sqrt(x)) – you need only test divisibility by the primes below sqrt(x),and not every integer in that range.