**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

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