Just trying to find out which of these five isprime functions is the fastest.
Timing five isprime functions (Python)
''' 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
'''
Gribouillis 1,391 Programming Explorer Team Colleague
vegaseat 1,735 DaniWeb's Hypocrite Team Colleague
slate 241 Posting Whiz in Training
Gribouillis 1,391 Programming Explorer Team Colleague
vegaseat 1,735 DaniWeb's Hypocrite Team Colleague
paddy3118 11 Light Poster
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.