0x0007 - Primality Testing

I’ve been doing some programs on Primality tests, and so far, have implemented some naive algorithms. Though not efficient, these are useful for quick implementations. Here I post some of them:

Method 1:

The simplest primality test is as follows: Given an input number n, check whether any integer m from 2 to n − 1 evenly divides n. If n is divisible by any m then n is composite, otherwise it is prime. The implementation in Python 2.7 in the form of a function is:

def is_prime1(n) :
    for m in range(2, n) :
        if n % m == 0: return False
    return True

Method 2:

Rather than testing all m up to n − 1, it is only necessary to test m up to : if n is composite then it can be factored into two values, at least one of which must be less than or equal to . The implementation is:

def is_prime2(n) :
    for m in range(2, int(sqrt(n))+1) :
        if n % m == 0: return False
    return True

Method 3:

The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does as well. Also, if n is found to be even, then it is not required to test further for primality. The implementation is:

def is_prime3(n) :
    if n == 2: return True
    if n % 2 == 0: return False
    for m in range(3, int(sqrt(n))+1, 2) :
        if n % m == 0: return False
    return True

Method 4:

The efficiency can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as testing all m.

def is_prime4(n) :
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0 or n % 3 == 0: return False

    sqrtN = int(sqrt(n))+1
    for i in range(6, sqrtN) :
        if n%(i-1) == 0 or n%(i+1) == 0: return False
    return True

Method 5:

The code in Method 4 can be improved if we rewrite it as:

def is_prime5(n) :
    if n == 2 or n == 3: return True
    if n < 2 or n % 2 == 0: return False
    if n < 9: return True
    if n % 3 == 0: return False

    r, f = int(sqrt(n)), 5

    while f <= r:
        if n % f == 0 or n % (f + 2) == 0: return False
        f += 6
    return True

Among all the five naive methods shown above, Method 5 has the best efficiency. Another idea to speed up the computation marginally is to replace i % 2 by i & 1*.*