# isprime function (Python)

Updated 2 Tallied Votes 3K Views

Just a small mildly optimized function to check if an integer is a prime number. For very large numbers use the Miller-Rabin primality test.

There have been questions why I used `not n & 1` to check for even integer n. The more tradional`n % 2 == 0` is about 30% slower. So I gained a tiny bit more speed.

``````''' isprime2.py
a function to check if a positive integer is prime
prime numbers are only divisible by unity and themselves
integers less than 2 and even numbers other than 2 are not prime
tested with Python27 and Python33  by  vegaseat  30aug2013
'''

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

# test ...
prime_list2 = []
for n in range(-50, 50):
if isprime2(n):
prime_list2.append(n)

print(prime_list2)

""" result ...
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
"""``````
HiHe 174

A little timing experiment:

``````''' timeit_isprime.py
check the speed of three isprime functions
'''

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

# note 9999991 is a prime number
print(isprime2(9999991))
print(isprime3(9999991))
print(isprime4(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))

''' result ...
3.4.1 (v3.4.1:c0e311e010fc, May 18 2014, 10:38:22) [MSC v.1600 32 bit (Intel)]
True
True
True
isprime2(9999991) takes 367.099 micro-seconds/pass
isprime3(9999991) takes 362.349 micro-seconds/pass
isprime4(9999991) takes 663.506 micro-seconds/pass
'''
``````
TrustyTony 888

Interesting HiHe, but I do not know if it is too biased to use only one number as case. Both isprime2 and isprime 3 seem to run more than my own isprime adapted as optimized from Project Euler (found in other prime tread recently posted to)

Tony

sneekula 969

Just a little faster than isprime2():

``````def isprime5(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
sqr = int(n**0.5)
f = 5
while f <= sqr:
if n%f == 0: return False
if n%(f+2) == 0: return False
# loop every 6th integer
f += 6
return True
``````
vegaseat 1,735

Testing the 2 "integer is even" expressions ...

``````''' timeit_lambda_simple101.py
using Python module timeit on a simple statement
(by default timeit turns off garbage collection)
'''

import timeit

# using default 1000000 passes --> micro-seconds/pass
elapsed = lambda stmt: timeit.Timer(stmt).timeit()

stmt = "not 9999991 & 1"  # True if even
# run and show the timeit test
print("'%s' took %0.3f micro-seconds" % (stmt, elapsed(stmt)))

stmt = "9999991 % 2 == 0"   # True if even
# run and show the timeit test
print("'%s' took %0.3f micro-seconds" % (stmt, elapsed(stmt)))

''' result (Python 3.4.1 64bit) -->
'not 9999991 & 1' took 0.033 micro-seconds
'9999991 % 2 == 0' took 0.054 micro-seconds
'''
``````
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.