isprime function (Python)

Updated vegaseat 2 Tallied Votes 3K Views Share

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]
"""
HiHe 174 Junior Poster

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 pyMod Team Colleague Featured Poster

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 Nearly a Posting Maven

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 DaniWeb's Hypocrite Team Colleague

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.