Prime Number Program 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 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
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
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
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
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
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
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
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
Getting Started
- ASCII Table
- Positive or Negative number: C | C++ | Java | Python
- Even or Odd number: C | C++ | Java | Python
- Sum of First N Natural numbers: C | C++ | Java | Python
- Sum of N natural numbers: C | C++ | Java | Python
- Sum of numbers in a given range: C | C++ | Java | Python
- Greatest of two numbers: C | C++ | Java | Python
- Greatest of the Three numbers: C | C++ | Java | Python
- Leap year or not: C | C++ | Java | Python
- Prime number: C | C++ | Java | Python
- Prime number within a given range: C | C++ | Java | Python
- Sum of digits of a number: C | C++ | Java | Python
- Reverse of a number : C | C++ | Java | Python
- Palindrome number: C | C++ | Java | Python
- Armstrong number : C | C++ | Java | Python
- Armstrong number in a given range : C | C++ | Java | Python
- Fibonacci Series upto nth term : C | C++ | Java | Python
- Find the Nth Term of the Fibonacci Series : C | C++ | Java | Python
- Factorial of a number : C | C++ | Java | Python
- Power of a number : C | C++ | Java | Python
- Factor of a number : C | C++ | Java | Python
- Finding Prime Factors of a number : C | C++ | Java | Python
- Strong number : C | C++ | Java | Python
- Perfect number : C | C++ | Java | Python
- Automorphic number : C | C++ | Java | Python
- Harshad number : C | C++ | Java | Python
- Abundant number : C| C++ | Java | Python
- Friendly pair : C | C++ | Java | Python
Login/Signup to comment
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")
Join our TA Support Group on Discord, where we will help you out with all your technical queries:
Discord
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.”)
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")
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”)
# 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))
#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')
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” )