## How to check if a number is prime in python / Various methods to check for a prime number in python

What is a prime number?
A number greater than 1 which is divisible only by 1 and itself is called a Prime number. By being 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.
There are different methods to check for a prime number in python. This post shall cover all of those.

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")```

Above program reads a number 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

Enter a number
12
12 is not a prime number

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 recursive approach
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 argument, 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.

Recursive function first 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. 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")```

Output

Enter a number
33
33 is not a prime number

Method 3: Using square root of number
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

Enter a number
37
37 is a prime number

That’s it on the different methods to check for a prime number in python. Keep visiting!!!

0

Never Miss an article !

Get the new post delivered straight into your inbox, enter your email and hit the button

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

codippa will use the information you provide on this form to be in touch with you and to provide updates and marketing.