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 tradionaln % 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]
"""
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
'''
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
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
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
'''
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.