How to Find Prime Number in Python – Examples and Explanation

Chart of prime numbersTo find a prime number in Python, we can have to create a special function solely for this purpose. There is no built-in function in Python for this purpose. By definition, a prime number is a natural integer number which is greater than 1 and has no positive divisors other than 1 and itself. In other words an integer number only divisible by 1 and itself.

Prime numbers start from 2 and their sequence is 2, 3, 5, 7, 11, 13, 17, 23… and up to the infinity. As of January 2016, the largest known prime number has 22,338,618 decimal digits. For further reading, you can follow this Wikipedia article about Prime Numbers.

There are various ways to find whether a number is a prime or not in Python programming language. Here is some better code snippet for this purpose.

 

Find a Prime Number in Python using Function

import math

def isPrimeNumber( n ):
    
    # Returns True if n is prime number else False

    # Make sure n is a positive integer
    # if not then make it positive intger
    n = abs(int(n))

    # ----- some simple and fast tests ---------
    
    # The number n is less 2 i-e 0 or 1
    if n < 2: return False
    
    # The number n is 2
    if n == 2: return True

    # The number n is even then not prime
    if n % 2 == 0: return False

    # Check odd numbers less than the square root of the given number n for possible factors 
    r = math.sqrt( n )
    
    # start from 3, we have already test for 0, 1 and 2
    x = 3 
    while x <= r:
        if n % x == 0: return False  # A factor was found, so number is not prime
        x += 2 # Increment to the next odd number

    # No factors found, so number is prime  
    return True 
    

# check for prime number
num = 23

if isPrimeNumber( num ):
    print( num , "is a prime number")
else:
    print( num , "is not a prime number")

Result:

23 is a prime number

Find Prime Number using Regular Express in Python Language

import re

def isPrimeNumber(n):    
    return not re.match(r'^1?$|^(11+?)\1+$',n*'1')    
    
# check for prime number
num = 21

if isPrimeNumber( num ):
    print( num , "is a prime number")
else:
    print( num , "is not a prime number")

Result:

21 is not a prime number

 

Find Prime Numbers in Range using List Comprehension in Python

# some arbitrary stopping point
EndTo = 20

primes = [prime for prime in range(2, EndTo)
          if prime not in
          [notAPrime for i in range(2, int(EndTo**0.5))
           for notAPrime in range(i * 2, EndTo, i)]]

print("Prime numbers between 2 and", EndTo)
print(primes)

Result:

Prime numbers between 2 and 20
[2, 3, 5, 7, 11, 13, 17, 19]

 

Find Prime Numbers in Range using Generator in Python

Note: range in Python 3.x is xrange in Python 2.x. Python 2 range is removed in Python 3. Now in Python 3 range is behaves like a generator. It is much faster and uses less memory.

from math import sqrt

n = 20
print("Prime numbers between 2 to", n)
for x in range(2, n):
    if not any(y for y in range(2, 1+int(sqrt(x))) if not x % y):
        print(x)

Result:

Prime numbers between 2 to 20
2
3
5
7
11
13
17
19

 

A good discussion on Prime Numbers in Python can also be found here.