Python Program to Check Prime Number
Given a positive integer N, The task is to write a Python program to check if the number is Prime or not in Python.
Examples:
Input: n = 11
Output: True
Input: n = 1
Output: False
Explanation: A prime number is a natural number greater than 1 that
has no positive divisors other than 1 and itself.
The first few prime numbers are {2, 3, 5, 7, 11, ….}.
Python Program to Check Prime Number
The idea to solve this problem is to iterate through all the numbers starting from 2 to (N/2) using a for loop and for every number check if it divides N. If we find any number that divides, we return false. If we did not find any number between 2 and N/2 which divides N then it means that N is prime and we will return True.
num = 11
# If given number is greater than 1
if num > 1:
# Iterate from 2 to n // 2
for i in range(2, (num//2)+1):
# If num is divisible by any number between
# 2 and n / 2, it is not prime
if (num % i) == 0:
print(num, "is not a prime number")
break
else:
print(num, "is a prime number")
else:
print(num, "is not a prime number")
Output
11 is a prime number
Time complexity: O(n)
Auxiliary space: O(1)
Find Prime Numbers with a flag variable
Instead of checking till n, we can check till √n because a larger factor of n must be a multiple of a smaller factor that has been already checked. Now let’s see the code for the first optimization method ( i.e. checking till √n )
from math import sqrt
# n is the number to be check whether it is prime or not
n = 1
# this flag maintains status whether the n is prime or not
prime_flag = 0
if(n > 1):
for i in range(2, int(sqrt(n)) + 1):
if (n % i == 0):
prime_flag = 1
break
if (prime_flag == 0):
print("True")
else:
print("False")
else:
print("False")
Output
False
Time complexity: O(sqrt(n))
Auxiliary space: O(1)
Check Prime Numbers Using Recursion
We can also find the number prime or not using recursion. We can use the exact logic shown in method 2 but in a recursive way.
from math import sqrt
def Prime(number,itr): #prime function to check given number prime or not
if itr == 1: #base condition
return True
if number % itr == 0: #if given number divided by itr or not
return False
if Prime(number,itr-1) == False: #Recursive function Call
return False
return True
num = 13
itr = int(sqrt(num)+1)
print(Prime(num,itr))
Output
True
Time complexity: O(sqrt(n))
Auxiliary space: O(sqrt(n))
Check the Prime Trial Division Method
def is_prime_trial_division(n):
# Check if the number is less than
# or equal to 1, return False if it is
if n <= 1:
return False
# Loop through all numbers from 2 to
# the square root of n (rounded down to the nearest integer)
for i in range(2, int(n**0.5)+1):
# If n is divisible by any of these numbers, return False
if n % i == 0:
return False
# If n is not divisible by any of these numbers, return True
return True
# Test the function with n = 11
print(is_prime_trial_division(11))
Output
True
Time complexity: O(sqrt(n))
Auxiliary space: O(sqrt(n))
Recommended Artilce – Analysis of Different Methods to find Prime Number in Python
Python Program to Check Prime Number Using a while loop to check divisibility
Initialize a variable i to 2, While i squared is less than or equal to n, check if n is divisible by i. If n is divisible by i, return False. Otherwise, increment i by 1. If the loop finishes without finding a divisor, return True.
import math
def is_prime(n):
if n < 2:
return False
i = 2
while i*i <= n:
if n % i == 0:
return False
i += 1
return True
print(is_prime(11)) # True
print(is_prime(1)) # False
Output
True False
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Python Program to Check Prime Number Using Math module
The code implements a basic approach to check if a number is prime or not, by traversing all the numbers from 2 to sqrt(n)+1 and checking if n is divisible by any of those numbers.
import math
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
n = 11
print(is_prime(n))
Output
True
Time complexity: O(sqrt(n))
The time complexity of the code is O(sqrt(n)) because we traverse all numbers in the range of 2 to sqrt(n)+1 to check if n is divisible by any of them.
Auxiliary Space: O(1)
The space complexity of the code is O(1) because we are only using a constant amount of memory to store the input number n and the loop variables.
Python Program to Check Prime Number Using sympy.isprime() method
In the sympy module, we can test whether a given number n is prime or not using sympy.isprime() function. For n < 264 the answer is definitive; larger n values have a small probability of actually being pseudoprimes.
N.B.: Negative numbers (e.g. -13) are not considered prime number.
# Python program to check prime number
# using sympy.isprime() method
# importing sympy module
from sympy import *
# calling isprime function on different numbers
geek1 = isprime(30)
geek2 = isprime(13)
geek3 = isprime(2)
print(geek1) # check for 30 is prime or not
print(geek2) # check for 13 is prime or not
print(geek3) # check for 2 is prime or not
# This code is contributed by Susobhan Akhuli
Output
False
True
True
Time Complexity: O(sqrt(n)), where n is the input number.
Auxiliary Space: O(1)
Contact Us