Home / Loop / Python / Recursion / Python Program to Check If a Number Is a Prime or Not

Python Program to Check If a Number Is a Prime or Not

in , ,
Prime number

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!





Labels: , ,