Python Program to Check Prime Number

Learn via video course
FREE
View all courses
Python Course for Beginners With Certification: Mastering the Essentials
Python Course for Beginners With Certification: Mastering the Essentials
by Rahul Janghu
1000
4.90
Start Learning
Python Course for Beginners With Certification: Mastering the Essentials
Python Course for Beginners With Certification: Mastering the Essentials
by Rahul Janghu
1000
4.90
Start Learning
Topics Covered

In this article, we will learn about prime numbers and how to check if a given number N is prime or not in Python.

A number is called a prime number if it is only divisible by 1 or N itself. The efficient Time complexity to check if a given number is prime or not is O(sqrt(n))O(sqrt(n)).

Program to Print Prime Number in Python

Any positive number greater than 1 is only divisible by two numbers, i.e., 1 and the number itself, which is called a prime number. The basic idea to know whether a given number is a prime number or not is to iterate from 1 and check whether it is divisible by any number smaller than it. If it is divisible by a number smaller than N, then it will not be a prime number.

There are different methods to check whether a given number is prime or not. Some of the major methods listed below as:

  1. Using a flag variable
  2. Using a for...else statement
  3. Using Recursion
  4. Check the Prime Trial Division Method
  5. Using a while loop to check divisibility
  6. Using Math module
  7. Using sympy.isprime() function

Python Program to Check Prime Number Using a flag variable

In this method, Instead of iterating through all numbers up to n when checking for factors, we can optimize by only checking up to the square root of n. This is because any larger factor of n has already been checked. So, we'll iterate only up to n.

Output:

Time Complexity O(sqrt(N))O(sqrt(N)),

Space Complexity: O(1)

Check Prime Numbers Using a for...else statement

This for...else method is also similar to the previous method; we first check each case using the if-else block and then pass the number to the for loop to check divisibility from any smaller number.

Output:

Time Complexity: O(sqrt(N))O(sqrt(N)),

Space Complexity: O(1)

Check Prime Numbers Using Recursion

We can also check whether a given number is prime using recursion. In this, we will start from sqrt(n)+1, and in each recursive call, we check whether it divides n or not.

Output:

Time Complexity: O(sqrt(N))O(sqrt(N)),

Space Complexity: O(sqrt(n))O(sqrt(n))

Find Prime Numbers Check the Prime Trial Division Method

In this method, we iterate over 2 to sqrt(n) and try to divide n from every number. If n is divisible by any of them, then the number will not be prime; otherwise, it will be a prime number.

Output:

Time Complexity: O(sqrt(N))O(sqrt(N)),

Space Complexity: O(1)

Find Prime Numbers Using a while loop to check divisibility

As we check a number is prime or not using the for loop, in similiar way, we can implment the while loop which is easy to implement as shown below:

Output:

Time Complexity: O(sqrt(N))O(sqrt(N)),

Space Complexity: O(1)O(1)

Python Program to Check Prime Number Using Using Math module

Using the math module present in Python, we can use its sqrt() function to iterate the number from 2 to sqrt(n) to check whether they divisible the given number.

Output:

Time Complexity: O(sqrt(N))O(sqrt(N)),

Space Complexity: O(1)O(1)

Python Program to Check Prime Number Using Using sympy.isprime() function

In Python, there is a module named sympy, which can be used to check whether a given number is prime or not. The sympy module has a isprime() predefined function in it to check a number's primeness. The answer is definitive for values of n less than 2^64; however, for larger n values, there is a small probability of them being pseudoprimes.

Output:

Time Complexity: O(sqrt(N))O(sqrt(N)),

Space Complexity: O(1)O(1)

Conclusion

  • In this article, we have seen prime number programs in python.
  • A number is called prime if only divisible by one and itself.
  • There are different methods to check a given number is prime or not.
  • In the Naive method, we can check if n is divisible by all smaller numbers greater than 1.
  • The time complexity to check whether a number is prime is O(sqrt(n))O(sqrt(n)).

Read More

  1. Python if…else Statement
  2. For Loop in Python
  3. Break, Pass and Continue Statement in Python
  4. Numbers in Python