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.
Python3
num = 11# If given number is greater than 1if num > 1: # Iterate from 2 to n / 2 for i in range(2, int(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") |
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 )
Python3
from math import sqrt# n is the number to be check whether it is prime or notn = 1# this flag maintains status whether the n is prime or notprime_flag = 0if(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") |
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.
Python3
from math import sqrtdef 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 = 13itr = int(sqrt(num)+1)print(Prime(num,itr)) |
True
Time complexity: O(sqrt(n))
Auxiliary space: O(sqrt(n))
Check the Prime Trial Division Method
Python3
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 = 11print(is_prime_trial_division(11)) |
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.
Python3
import mathdef is_prime(n): if n < 2: return False i = 2 while i*i <= n: if n % i == 0: return False i += 1 return Trueprint(is_prime(11)) # Trueprint(is_prime(1)) # False |
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.
Python3
import mathdef 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 Truen = 11print(is_prime(n)) |
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.
Python3
# Python program to check prime number# using sympy.isprime() method# importing sympy modulefrom sympy import *# calling isprime function on different numbersgeek1 = isprime(30)geek2 = isprime(13)geek3 = isprime(2)print(geek1) # check for 30 is prime or notprint(geek2) # check for 13 is prime or notprint(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)
