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

1,265 Views
``````''' 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

'''``````
vegaseat

Scientist

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

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
>>> 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
``````

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.

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

@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!

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

The Miller Rabin test took about 11 microseconds.

Try Rosetta Code for something10x faster here