Program to Check Prime Number

Python Program to Check a Number is Prime or Not

/ Python / By

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:

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: