Grab the opportunity to learn all effective java programming language concepts from basic to advance levels by practicing these Java Program Examples with Output

**Factors of a number:**

When two whole numbers are multiplied, the result is a product. The factors of the product are the numbers we multiply.

In mathematics, a factor is a number or algebraic expression that equally divides another number or expression, leaving no remainder.

**Prime Number:**

A prime number is a positive integer greater than 1 that has no other variables except 1 and the number itself. Since they have no other variables, the numbers 2, 3, 5, 7, and so on are prime numbers.

Given a number , the task is to check whether the given number is prime or not.

**Examples:**

**Example 1:**

**Input:**

number =5

**Output:**

The given number 5 is prime number

**Example 2:**

**Input:**

number =8

**Output:**

The given number 8 is not prime number

**Example 3:**

**Input:**

number =2

**Output:**

The given number 2 is not prime number

## Program to Check Prime Number in Python Programming

Below are the ways to check whether the given number is prime or not:

- Using for loop to loop from 2 to N-1 using flag or temp variable
- Using For Else Statement
- Limitations of above methods in terms of Time Complexity
- Solution Approach for Efficient Approach
- Implementation of Efficient Approach

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

### 1)Using for loop to loop from 2 to N-1 using flag or temp variable

To see if there are any positive divisors other than 1 and number itself, we divide the input number by all the numbers in the range of 2 to (N – 1).

If a divisor is found, the message “number is not a prime number” is displayed otherwise, the message “number is a prime number” is displayed.

We iterate from 2 to N-1 using for loop.

**Below is the implementation:**

# given number number = 5 # intializing a temporary variable with False temp = False # We will check if the number is greater than 1 or not # since prime numbers starts from 2 if number > 1: # checking the divisors of the number for i in range(2, number): if (number % i) == 0: # if any divisor is found then set temp to true since it is not prime number temp = True # Break the loop if it is not prime break if(temp): print("The given number", number, "is not prime number") else: print("The given number", number, "is prime number")

**Output:**

The given number 5 is prime number

**Explanation:**

We checked whether a number is prime or not in this program . Prime numbers are not those that are smaller than or equal to one. As a result, we only go forward if the number is greater than one.

We check whether a number is divisible exactly by any number between 2 and number – 1. We set temp to True and break the loop if we find a factor in that range, indicating that the number is not prime.

We check whether temp is True or False outside of the loop.

Number is not a prime number if it is True.

If False, the given number is a prime number.

### 2)Using For Else Statement

To check if number is prime, we used a for…else argument.

It is based on the logic that the for loop’s else statement runs if and only if the for loop is not broken out. Only when no variables are found is the condition satisfied, indicating that the given number is prime.

As a result, we print that the number is prime in the else clause.

**Below is the implementation:**

# given number number = 5 # We will check if the number is greater than 1 or not # since prime numbers starts from 2 if number > 1: # checking the divisors of the number for i in range(2, number): if (number % i) == 0: # if any divisor is found then print it is not prime print("The given number", number, "is not prime number") # Break the loop if it is not prime break else: print("The given number", number, "is prime number") # if the number is less than 1 then print it is not prime number else: print("The given number", number, "is not prime number")

**Output:**

The given number 5 is prime number

### 3)Limitations of above methods in terms of Time Complexity

In these two methods the loop runs from 2 to number N-1.

Hence we can say that the time complexity of above methods are O(n).

What if the number is very large?

Like 10^18 the above methods takes nearly 31 years to execute.

Then How to avoid this?

We can see that the factors of the numbers exist from 1 to N/2 except number itself.

But this also takes nearly 15 yrs to execute.

So to above this we loop till square root of N in next method which gives Time Complexity O(Sqrt(n)).

### 4)Solution Approach for Efficient Approach

We will improve our program by reducing the number range in which we search for factors.

Our search range in the above program is 2 to number – 1.

The set, range(2,num/2) or range(2,math.floor(math.sqrt(number)) should have been used. The latter range is based on the requirement that a composite number’s factor be less than its square root. Otherwise, it’s a prime number.

### 5)Implementation of Efficient Approach

In this function, we use Python’s math library to calculate an integer, max_divisor, that is the square root of the number and get its floor value. We iterate from 2 to n-1 in the last example. However, we reduce the divisors by half in this case, as shown. To get the floor and sqrt functions, you’ll need to import the math module.

**Approach:**

- If the integer is less than one, False is returned.
- The numbers that need to be verified are now reduced to the square root of the given number.
- The function will return False if the given number is divisible by any of the numbers from 2 to the square root of the number.
- Otherwise, True would be returned.

**Below is the implementation:**

# importing math module import math # function which returns True if the number is prime else not def checkPrimeNumber(number): if number < 1: return False # checking the divisors of the number max_divisor = math.floor(math.sqrt(number)) for i in range(2, max_divisor+1): if number % i == 0: # if any divisor is found then return False return False # if no factors are found then return True return True # given number number = 5 # passing number to checkPrimeNumber function if(checkPrimeNumber(number)): print("The given number", number, "is prime number") else: print("The given number", number, "is not prime number")

**Output:**

The given number 5 is prime number

**Related Programs**:

- python program to find if a number is prime or not prime using recursion
- java program to check whether a number is prime or not
- python program to check if a string is palindrome or not
- python program to check if a string is a pangram or not
- python program to check whether the given number is strong number or not
- python program to check whether the given number is perfect number or not
- python program to check whether a string is a palindrome or not using recursion