Check prime number program in python

There are different methods to check for a prime number in python. This article shall explain three programs with example.

What is a prime number?
A number greater than 1 which is divisible only by 1 and itself is called a Prime number. Divisible means when a number is divided by another number the remainder is 0.

Thus, the only factors of a prime number are 1 and the number itself. Remember that 1 is not considered a prime number.

Method 1: Using for-else block
A for-else block consists of a for loop block followed by the else block where else block is only executed when the for loop is not terminated by a break statement.

In other words, else block will execute only when the loop is not fully executed or terminated in between. Code follows.

# read number from keyboard
input_value = input("Enter a number\n")
# convert it to integer
number = int(input_value)
if number > 1:
    # loop from 2 to (number - 1)
    for i in range(2, number):
        # divide the number and check for remainder
        if (number % i) == 0:
            # number is divisible by some other number
            print(number, "is not a prime number")
            # terminate loop
            break
    else:
        print(number, "is a prime number")
else:
    # number is not greater than 1
    print(number, "is not a prime number")

Explanation
Above program reads a number as input from user which needs to be checked for prime number from keyboard and loops from 2 till (number – 1).

In every iteration, it divides the number to be checked with the current loop index.
If the remainder of division is 0(number is divisible by some other number except itself as well), it means that the number is not prime.
Loop is terminated using break statement.

If the number is prime, it is not divisible by any other number and the loop is fully executed. This means that number is prime and else block is executed in this case.

Output of execution of this code is as follows

Using for loop
It is also possible to omit the else block and check for prime number using only for loop.

Create a function containing the for loop as explained above. This function should accept the integer to be checked for prime number.
In place of break, return False from the function indicating that the number is not prime. If the loop completes successfully, return True indicating that the number is prime.

Code is given below.

# Checks if the number is prime
def isPrime(number):
    # number is less than 2, not prime
    if number < 2:
        return False
    # 2 is a prime number
    elif number == 2:
        return True
    # iterate from 2 till the number
    for i in range(2, number):
        # number is divisible by some other number
        if number % i ==0:
            return False
    # loop completed, number is prime
    return True

Method 2: Using recursion
This method is a recursive variant of the above method.
It defines a recursive function which takes the number to be tested and a divisor as arguments, checks for the supplied argument as being a prime number and returns True if it is a prime number, False otherwise.

Divisor(or second argument) is 2 when the function is first called and is incremented by 1 in each successive function call.

Code follows

# Checks if the number is prime
def isPrime(num, divisor = 2):
    # not prime if number is 1
    if num == 1:
        return False
    # number and divisor are both same
    elif(num == divisor):
        return True
    # number is divisible by divisor and they both are not same
    elif(num % divisor == 0):
        return False
    else:
        # call this method again with divisor incremented by 1
        return isPrime(num, divisor + 1)


# read number from keyboard
input_value = input("Enter a number")
# convert it to integer
number = int(input_value)

# check if number is prime
if isPrime(number):
    print(number, "is a prime number")
else:
    print(number, "is not a prime number")

Explanation
isPrime() is a recursive function.
First it checks if the given number is 1 which means that the number is not prime. It returns False.

Secondly, it checks if the given number and divisor are equal. This means that the number is not divisible by any other number other than itself, that is, it is prime. It returns True.

Thirdly, it divides the number by the divisor and checks the remainder. If the remainder is 0 means that the number is divisible by the divisor and it is not prime. Thus, the function returns False.

Finally, if all the above conditions are not met, then the function calls itself again with divisor(or second argument) incremented by 1.
Output

Method 3: Using square root
Both the above methods check for a number being prime by iterating from 2 till the number.
This method can be used for smaller numbers but for large numbers, it becomes inefficient and takes more time.

A more efficient method is to divide the number to be checked by all integers from 2 till the the square root of the number.
If any integer divides the number then it is non-prime. If none of the integers divide the number, then the number is prime. This way, the count of iterations is reduced considerably resulting in increased performance.

Code follows

# Checks if the number is prime
def isPrime(number):
    # 1 is not a prime number
    if number <= 1:
        return False
    # loop from 2 till the square root of number
    for x in range(2, int(number ** 0.5) + 1):
        # check the remainder of division of number with current loop index
        if number % x == 0:
            return False
    return True


# read number from keyboard
input_value = input("Enter a number")
# convert it to integer
number = int(input_value)

# check if number is prime
if isPrime(number):
    print(number, "is a prime number")
else:
    print(number, "is not a prime number")

Output is

Hope the article was useful and explanatory, don’t forget to hit the clap below.