Python Program to Check Prime Number

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))$,

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))$,

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))$,

Space Complexity: $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))$,

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))$,

Space Complexity: $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))$,

Space Complexity: $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))$,

Space Complexity: $O(1)$

Read More

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