Check Whether a Number is a Prime or Not in Python

Check Whether a Number is a Prime or Not in Python

Given an integer input the objective is to write a program to Check Whether a Number is a Prime or Not in Python Language.

Example
Input : 11
Output : 11 is a Prime
Check Whether a Number is Prime or Not in Python

Check Whether a Number is a Prime or Not

Given an integer input for a number, the objective is to check whether or not the number is a prime. In order to do so we keep checking with all the numbers until square root of the number itself for factors of the number input. If found any, the number is not a prime. Here are some of the methods given to solve the above mentioned problem in python language,

  • Method 1: Simple iterative solution
  • Method 2: Optimization by break condition
  • Method 3: Optimization by n/2 iterations
  • Method 4: Optimization by √n
  • Method 5: Optimization by skipping even iteration
  • Method 6: Basic Recursion technique

We’ll discuss the above mentioned methods in detail in the sections below.

Method 1: Simple iterative solution

Working

In this method we’ll use simple if-else statements and for loop to iterate though all the number in a given range while checking for factors of the number.

For a given integer input we check,

  • If the number is greater than 2.
  • If the number has any factors in the range [2,number].
  • If any off the above conditions are satisfied, the number isn’t a Prime.

Python Code

Run
num = 15
flag = 0
for i in range(2,num+1):
  if num%i==0:
    flag = 1
    break
if flag == 1:
  print('Not Prime')
else:
  print("Prime")

Output

Not Prime

Method 2: Optimization by break condition

Working

In this method we’ll check if the number is divisible by any other number except the number itself and 1. We eliminate the possibilities using if-else statements.

For a given integer input, we check for the following

  • If number is smaller than 2.
  • If the number has any other factors besides itself and 1.
  • If any other the conditions are satisfied, the number is not a Prime.

Python Code

Run
num = 15
flag = 0
if num<2:
  flag = 1
else:
  for i in range(2,num+1):
    if num%i==0:
      flag = 1
      break

if flag == 1:
  print('Not Prime')
else:
  print("Prime")

Output

Not Prime

Method 3: Optimization by n/2 iterations

Working

In this method we’ll check if the number input have any factors within the range of 2 to number/2. Any number has it’s lowest factor after 1 if any, in the range[2,number/2].

For a given integer input we check for the following,

  • If the number input has factors in the range [2, number/2]. It’s not a Prime of the above condition is true.

Python Code

Run
num = 15
flag = 0
if num<2:
  flag = 1
else:
  for i in range(2,int((num/2)+1)):
    if num%i==0:
      flag = 1
      break

if flag == 1:
  print('Not Prime')
else:
  print("Prime")

Output

Not Prime

Method 4: Optimization by √n

Working

In this method we’ll run the loop until the square root of the given number input as all the smallest factor of any number if any, lay in the interval [0, sqrt(number)]. Therefore, we’ll check for the factors within the above mentioned interval.

For the given input integer we check for the following,

  • If the number is divisible by  any number in the interval [2,sqrt(number)], if so then it’s not a prime.

Python Code

Run
num = 7
flag = 0
if num<2:
  flag = 1
else:
  for i in range(2,int(pow(num,0.5)+1)):
    if num%i==0:
      flag = 1
      break

if flag == 1:
  print('Not Prime')
else:
  print("Prime")

Output

Prime

Method 5: Optimization by skipping even iteration

Working

In this method we’ll skip the even iterations as any even number can’t be a Prime. This way we’ll reduce the comparisons by 50%. To do so we’ll increase the step to +1.

For a given integer input we check for,

  • If the number is 2 as two is the only even prime.
  • Check every other number until square root of the number input looking for it’s factors.

Python Code

Run
num = 15
flag = 0
if num<2:
  flag = 1
elif num == 2:
  flag = 0
else:
  for i in range(3,int(pow(num,0.5)+1),2):
    if num%i==0:
      flag = 1
      break

if flag == 1:
  print('Not Prime')
else:
  print("Prime")

Output

Not Prime

Method 6: Basic Recursion technique

Working

In this method we use the concept of recursion, to know more about recursion check out recursion in python.

For the given integer input we perform the following

  • Declare a recursive function checkPrime() with base cases as follows
    • if number == iter, return True.
    • if number < 2, return False.
    • if number % iter == 0, return False.
  • Set the Recursive step call as checkPrime(number,iter+1).

Python Code

Run
num = 15
def checkPrime(num,iter=2):
  if num == iter:
    return True
  if num%iter==0:
    return False
  if num<2:
    return False
  return checkPrime(num,iter+1)
if checkPrime(num)==True:
  print("Prime")
else:
  print("Not Prime")

Output

Not Prime

Getting Started

One comment on “Check Whether a Number is a Prime or Not in Python”


  • madaneshankar6

    num =int(input())
    flag=False

    for i in range(2,num+1):
    if i==num:
    continue
    if num%i==0:
    flag=True
    break
    print(” not prime” if flag else “prime” )