Prime Number Program in Python

June 29, 2023

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):
  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

Python Code

Run 
num = 15
flag = 0
if num<2:
  flag = 1
else:
  for i in range(2,num):
    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

Greatest of the Three numbers

Leap year or not

Prime number within a given range

Sum of digits of a number

Reverse of a number

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.

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Getting Started

8 comments on “Prime Number Program in Python”


  • NIGAN

    In Method 5: Optimization by skipping even iteration:
    This program gives the wrong output for even numbers as
    it doesn’t change the flag value to 1 when the input is even
    We need to add an extra elif condition (num%2 == 0)
    to change the flag value to 1 when input is even

    Program :
    num = 2
    flag = 0
    if num<2:
    flag = 1
    elif num == 2:
    flag = 0
    elif num%2==0:
    flag = 1
    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")

    0

  • realrishiiscool Gaming

    n = float(input(“Enter a number: “))
    prime = True

    for i in range(2,int(n/2)):
    if n % i == 0:
    prime = False
    break

    if prime:
    print(“It is a prime number.”)
    else:
    print(“It is not a prime number.”)

    0

  • Raghvendra Singh Shekhawat

    number = int(input(“Enter the number: “))
    prime = 0
    for i in range(2,number):
    if number%i == 0:
    prime = 1
    break

    if number <= 2:
    print("prime")
    elif prime == 1:
    print("no prime")
    elif prime == 0:
    print("prime")

    0

  • NANDHAKUMAR

    num=int(input(“enter a number: “))
    count=0
    for i in range(1,num+1):
    if num%i==0:
    count+=1
    if count>2:
    print(“it’s not prime”)
    else:
    print(“it’s prime”)

    3

  • PRIYA

    # By Factors
    def check_factor(n):
    factors=[i for i in range(2,n) if n%i==0]
    if len(factors)==0:
    return “Prime Number”
    return “Not a Prime Number”

    user_n=int(input(“Enter number: “))
    print(user_n,”is a”,check_factor(user_n))

    0

  • B21_Mohammad

    #python program to check prime Number or not
    n=int(input(‘Enter a number :’))
    count=0 #Intialization
    i=1
    while(i<=n): #condition
    if (n%i==0):
    count+=1 #increment or decrement
    i+=1
    if (count==2):
    print(f'number {n} is a prime Number')
    else:
    print(f'number {n} is not a prime number')

    1

  • 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” )

    0