Primality Test In Python

I'm trying to do a simple primality test in Python. Accoding to Wikipedia, a primality test is the following: Given an input number n, check whether any integer m from 2 to n −

Solution 1:

Have a look at the Miller–Rabin primality test if a probabilistic algorithm will suffice. You could also prove a number to be prime, with for instance Elliptic Curve Primality Proving (ECPP), but it takes more effort.

A simple trial division algorithm is the following

defprime(a):
     returnnot (a < 2orany(a % x == 0for x inrange(2, int(a ** 0.5) + 1)))

Edit: Here's a more educational version because the first solution is very condensed and perhaps harder to read:

from math import sqrt
defprime(a):
    if a < 2: returnFalsefor x inrange(2, int(sqrt(a)) + 1):
        if a % x == 0:
            returnFalsereturnTrue

I've substituted in sqrt(a) in place of a ** 0.5 to make things more clear. The square root is used to not look at more factors than we have to.

Solution 2:

In brief, your isprime(x) checks whether the number is odd, exiting right after if x % 2 == 0.

Try a small change so that you would actually iterate:

defisprime(x):
    for i inrange(2, x-1):
        if x % i == 0:
            returnFalseelse:
        returnTrue

Note that else: is now part of the for loop rather than if statement.

Solution 3:

Your function actually returns whether your number is odd.

Indeed, what you're doing is you're checking whether 2 divides your number, and return immediately. You never check for the other numbers.

What you need to do is take this return true out of the if's else clause and the for loop back into the main function body.

On a sidenote, If you're looking for the primes lower than a given number, you could store the primes you found in memory and then only try dividing you new number by those primes ! (because if d is composite and divides q, then p exists such that p is prime and p divides q).

Solution 4:

The problem is that you put return False in the else clause rather than at the end of the function. So your function will return right after the first divisor is checked, rather than going on to check other divisors.

Here is a simple primality test similar to yours:

defis_prime(n):
    d = 2while d * d <= n:
        if n % d == 0:
            returnFalse
        d += 1return n > 1