Table of Contents

Python code to check whether a number is prime or not

In this article, we will take three different approaches for Primality Test

  • Brute Force Algorithmic approach
  • Optimizing Brute Force Algorithm
  • Using the AKS Primality Test

 

Python code for Primality test using Brute Force Algorithmic approach

We know that any number is a prime number if it has no positive divisor other than one. Based on the definition, the simplest approach is to check if the number is divisible from 2 to n-1. Below is the Python code using the Brute Force Algorithmic approach.

Code: 
#Python code Primality test using Brute Force Algorithmic approach

number_entered = input("Enter the number for Primality Test: ")
number = int(number_entered)

if number < 2:
    print("Number is less than 2")
    exit()

i = 2
x = number - 1
for i in range(2, number - 1):
    if number % i == 0:
        print("Number is not Prime")
        exit()


print(number, " is a Prime number")

 

Output: 
Enter the number for Primality Test: 359
359  is a prime number

 

Python Code Editor Online - Click to Expand

 

Python code for Primality test using Optimization of Brute Force Algorithm

Instead of checking the primality of a number by running the loop from 2 to n-1, we can check the divisibility of the number only for each number between 2 and number/2.

Code: 
#Python code Primality test using Optimized Brute Force Algorithmic approach

number_entered = input("Enter the number for Primality Test: ")
number = int(number_entered)

if number < 2:
    print("Number is less than 2")
    exit()
if number == 2:
    print("Number is Prime")
    exit()

i = 2
x = int(number/2)
for i in range(2, int(number/2)):
    if number % i == 0:
        print("Number is not Prime, it is divisible by: ",i)
        exit()


print(number, " is a Prime number")

 

Output: 
Enter the number for Primality Test: 101
101  is a Prime number
Python Code Editor Online - Click to Expand

Python code for Primality test Using the AKS Primality Test 

AKS Test: Check the divisibility for each number between 2 and sqrt(number).

i=2 to the range i<=sqrt(number)

One more optimization can be added to AKS test based on the fact that if a given number is even, then a number cannot be prime. If a number is divisible by 2, then it is divisible by multiple of 2 to the range n/2. So we only need to check if it is divisible by 2 and the remaining list to check is for odd numbers of form 2*x + 1 from the range

i=3 to the range i<=sqrt(number) with a step increment of i += 2
Code: 
# Python code Primality test by AKS with additional optimization

from math import sqrt

number_entered = input("Enter the number for Primality Test: ")
number = int(number_entered)

if number < 2:
    print("Number is less than 2")
    exit()
if number == 2:
    print("Number is Prime")
    exit()
if number % 2 == 0:
    print("Number is not Prime, it is divisible by 2")
    exit()

i = 3
x = int(sqrt(number))
for i in range(3, int(sqrt(number)), 2):
    if number % i == 0:
        print("Number is not Prime, it is divisible by: ", i)
        exit()

print(number, " is a Prime number")

 

Output: 
Enter the number for Primality Test: 709
709  is a Prime number
Python Code Editor Online - Click to Expand

 

 

Enjoy Python Code By Pythonbaba 🙂