Python programs to check if a number is a prime or not have been shown here. A positive number $n$ is called a prime, if it does not have any divisor except $1$ and $n$. For example if $n = 13$, it is prime but if $n = 10$, it is not prime as $10$ is divisible by $2$ and $5$ apart from $1$ and $10$. The algorithm, pseudocode and time complexity of the program have been shown below.

## 1. Algorithm to check if a number is a prime or not

1. Take a positive number n as input.

2. Check for each i $\in$ [2, $\sqrt{n}$], if n is divisible by i

3. If step 2 is true for atleast one i, then n is not a prime.

4. If step 2 is false for each i, then n is a prime.

## 2. Pseudocode to check if a number is a prime or not

Input : A postive number $n$

Output : $n$ is a prime or not a prime

1. Procedure checkPrime($n$):

2. $flag \leftarrow 0$

3. Repeat for $i \in [2, \sqrt{n}]$:

4. If $n \mod i$ = 0:

5. $flag \leftarrow 1$

6. break

7. If $n = 1$

8. Return "not a prime"

9. Else:

10. If $flag = 1$:

11. Return "not a prime"

12. Else:

13. Return "a prime"

14. End Procedure

## 3. Time complexity to check if a number is a prime or not

Time Complexity: O($\sqrt{n}$)

Where n is the input number.

## 4. Python Program & output to check if a number is a prime or not using iteration

Code has been copied
# *************************************
#         alphabetacoder.com
# Python program to check if a number
# is a prime or not using iteration
# *************************************

# take input of the number
n = int(input("Enter the number = "))

# initialize
flag = 0

# check if n is a prime or not
# If n has divisor between 2 and
# square root of n, then
# n is not prime else n is prime
for i in range(2, (int(n**0.5) + 1)):
if n % i == 0:
flag = 1  # mark as not prime
break  # exit from loop

# dispay the result
if n == 0 or n == 1:
print(n, "is neither a prime nor a composite!")
else:
if flag == 0:
print(n, "is a prime!")
else:
print(n, "is not a prime!")


Output

Enter the number = 13

13 is a prime!

## 5. Python Program & output to check if a number is a prime or not using recursion

Code has been copied
#*************************************
#       alphabetacoder.com
# Python program to check if a number
# is a prime or not using recursion
#*************************************

# recursive function to check
# if a number is prime or not
# check divisor upto square root of num
def check_prime(num, i):
# return 1, as num is prime
if i > num**0.5:
return 1
# return 0, as num is not prime
if num % i == 0:
return 0
# call function
return check_prime(num, i + 1)

# main function
def main():
# take input of the number
n = int(input("Enter the number = "))

# check if n is a prime or not
# by calling the function
# if the function returns 1,
# it is considered prime else
# it is considered not prime
if n == 0 or n == 1:
print(n,"is neither a prime nor a composite!")
else:
if check_prime(n, 2) == 1:
print(n,"is a prime!")
else:
print(n,"is not a prime!")

# driver code
main()


Output

Enter the number = 97

97 is a prime!