Timing five isprime functions (Python)

vegaseat 1 Tallied Votes 2K Views Share

Just trying to find out which of these five isprime functions is the fastest.

''' timeit_isprime.py
check the speed of five isprime functions
tested with Python34   by  vegaseat (dns)  16may2015
'''

import timeit
import sys

print(sys.version)

def isprime2(n):
    '''
    check if integer n is a prime, return True or False
    '''
    # 2 is the only even prime
    if n == 2:
        return True
    # integers less than 2 and even numbers other than 2 are not prime
    elif n < 2 or not n & 1:
        return False
    #if n % 3 == 0: return False
    # loop looks at odd numbers 3, 5, 7, ... to sqrt(n)
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

def isprime3(n):
    '''
    check if integer n is a prime, return True or False
    '''
    # 2 is the only even prime
    if n == 2:
        return True
    # integers less than 2 and even numbers other than 2 are not prime
    if n < 2:
        return False
    if not n & 1:  # even numbers
        return False
    # loop looks at odd numbers 3, 5, 7, ... to sqrt(n)
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

def isprime4(n):
    '''
    check if integer n is a prime, return True or False
    uses a while loop, another way to write it, but is slower
    '''
    # 2 is the only even prime
    if n == 2:
        return True
    # integers less than 2 and even numbers other than 2 are not prime
    if n < 2:
        return False
    if n % 2 == 0:  # even numbers
        return False
    k = 3
    while k * k <= n:
         if n % k == 0:
             return False
         k += 2
    return True

def isprime5(n):
    # deal with low primes and even numbers
    if n in (2,3,5,7,): return True
    if n < 2 or n%2 == 0: return False
    if n%3 == 0: return False
    # need divisors only up to sqrt(x) or n**0.5
    sqr = int(n**0.5)
    div = 5
    while div <= sqr:
        if n%div == 0: return False
        if n%(div+2) == 0: return False
        # loop every 6th integer
        div += 6
    return True

def isprime6(n):
    # no negative numbers
    n = abs(n)
    # deal with primes under 5
    if n in (2,3,):
        return True
    # the rest of the primes are multiples of 6 plus or minus 1
    # this eliminate 2/3 of the remaining candidates
    if (n < 5) or ((n % 6) not in (1, 5,)):
         return False
    # need divisors only up to math.sqrt(x)+2 (same as n**0.5+2)
    for div in range(6, int(n**0.5+2), 6):
        if (n % (div+1) == 0) or (n % (div-1) == 0):
            return False
    return True

# note 9999991 is a prime number, use for testing
print("isprime2(9999991) = {}".format(isprime2(9999991)))
print("isprime3(9999991) = {}".format(isprime3(9999991)))
print("isprime4(9999991) = {}".format(isprime4(9999991)))
print("isprime5(9999991) = {}".format(isprime5(9999991)))
print("isprime6(9999991) = {}".format(isprime6(9999991)))


stmt = 'isprime2(9999991)'
find_function = 'from __main__ import isprime2'
t = timeit.Timer(stmt, setup=find_function)
# doing 1000 passes * 1000 gives the time in microseconds/pass
elapsed = (1000 * t.timeit(number=1000))
print("%s takes %0.3f micro-seconds/pass" % (stmt, elapsed))

stmt = 'isprime3(9999991)'
find_function = 'from __main__ import isprime3'
t = timeit.Timer(stmt, setup=find_function)
# doing 1000 passes * 1000 gives the time in microseconds/pass
elapsed = (1000 * t.timeit(number=1000))
print("%s takes %0.3f micro-seconds/pass" % (stmt, elapsed))

stmt = 'isprime4(9999991)'
find_function = 'from __main__ import isprime4'
t = timeit.Timer(stmt, setup=find_function)
# doing 1000 passes * 1000 gives the time in microseconds/pass
elapsed = (1000 * t.timeit(number=1000))
print("%s takes %0.3f micro-seconds/pass" % (stmt, elapsed))

stmt = 'isprime5(9999991)'
find_function = 'from __main__ import isprime5'
t = timeit.Timer(stmt, setup=find_function)
# doing 1000 passes * 1000 gives the time in microseconds/pass
elapsed = (1000 * t.timeit(number=1000))
print("%s takes %0.3f micro-seconds/pass" % (stmt, elapsed))

stmt = 'isprime6(9999991)'
find_function = 'from __main__ import isprime6'
t = timeit.Timer(stmt, setup=find_function)
# doing 1000 passes * 1000 gives the time in microseconds/pass
elapsed = (1000 * t.timeit(number=1000))
print("%s takes %0.3f micro-seconds/pass" % (stmt, elapsed))


''' result ...
3.4.2 |Continuum Analytics, Inc.| (default, Oct 21 2014, 17:42:20) 
[GCC 4.2.1 (Apple Inc. build 5577)]
isprime2(9999991) = True
isprime3(9999991) = True
isprime4(9999991) = True
isprime5(9999991) = True
isprime6(9999991) = True
isprime2(9999991) takes 162.309 micro-seconds/pass
isprime3(9999991) takes 162.340 micro-seconds/pass
isprime4(9999991) takes 280.765 micro-seconds/pass
isprime5(9999991) takes 135.013 micro-seconds/pass
isprime6(9999991) takes 127.583 micro-seconds/pass

'''
slate 241 Posting Whiz in Training

I hope nobody thinks these algos are used in the real world. There are much better algos to determine if a number is prime. Since the beginning of the 20th century.

These functions are good to understand how to program, and how to program in python. They are hardly usable for anything real. Harder euler problems cannot be solved with them.

commented: Indeed +14
Gribouillis 1,391 Programming Explorer Team Colleague

There are good functions in the nzmath module. Here is a session with python 2.7 in linux

>>> import nzmath
>>> from nzmath.prime import primeq
/usr/local/lib/python2.7/dist-packages/nzmath/config.py:328: UserWarning: no datadir found
  warnings.warn('no datadir found')
>>> primeq(9999991)
True
>>> import timeit
>>> find_function = 'from __main__ import primeq'
>>> stmt = 'primeq(9999991)'
>>> t = timeit.Timer(stmt, setup=find_function)
>>> elapsed = (1000 * t.timeit(number=1000))
>>> print("%s takes %0.3f micro-seconds/pass" % (stmt, elapsed))
primeq(9999991) takes 13.109 micro-seconds/pass
vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

I guess, we all need to just google and stop posting.

For some odd reason I could never get nzmath to go, all I got is a fistful of error messages.

The standard Miller Rabin isprime function is plenty fast for me. It is included in the "math/big" package in Google's Go language that I use use for high speed code.

slate 241 Posting Whiz in Training

There is my python implementation in this thread as an answer. Nobody bothered to read it ...

Gribouillis 1,391 Programming Explorer Team Colleague

@slate I already saw such primality tests. Your code lacks a good reference to the mathematical algorithm used. It would be easier to understand the way it works with the help of some theory.

I guess, we all need to just google and stop posting.

@vegaseat I think this is more and more true for some standard problems. Instead of coding ourselves, we are better off selecting the best solution among existing modules. In this case, you may want the primality test without the rest of the module (for example because the module won't work on your computer). A good idea would be to extract the primality test out of this package and write a version in a code snippet!

vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

@slate:
checked out your function with a modest failure rate and got about 80 microseconds.

The Miller Rabin test took about 11 microseconds.

paddy3118 11 Light Poster

Try Rosetta Code for something10x faster here

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.