Prime Number In Python

In this tutorial, We will learn about how to check the prime number in python. We will also discuss the efficiency of our solution as well as try to optimize that.we will also write a program to find prime numbers in a given interval. So let’s start with the math definition of a prime number.

Math Definition Of Prime Number :

A prime number is a natural number greater than 1 and is only divisible itself and 1 eg (2, 3, 5, 7, 11).

A prime number is a natural number greater than 1 and is only divisible itself and 1 eg (2, 3, 5, 7, 11).

Program To Find Prime Number In Python

Now let’s write code to check prime number in python.

# program to check prime number in python
def check_prime(number):
    # IF number is less than 2 then return False
    if number < 2:
        return False

    # Loop from 2 to N
    for i in range(2,number):
        # Check if number is divisible by i
        if number%i == 0:
            # if divisible then it's not prime
            return False
    # If number is not divisible by anything means it's prime
    return True


num = int(input("Enter Number : "))
is_prime = check_prime(num)

if is_prime:
    print(num,"Is Prime")
else:
    print(num,"Is Not Prime")

Save and run the above code . you should see the following output.

Output :

program to find prime number in python output.

Note: The above solution is not very efficient (Time complexity: O(n) ). We don't need to check all numbers between 1 and N.

We only need to loop up to the square root of the number. this will decrease our time complexity to O(log(n)) which is a lot efficient than the previous version.

So let's Implement That.

Efficient Version :

def check_prime(number):
    # IF number is less than 2 then return False
    if number < 2:
        return False

    #Find Square root
    root = int(number**0.5) + 1
    for i in range(2,root):
        # Check if number is divisible by i
        if number%i == 0:
            # if divisible then it's not prime
            return False
    # If number is not divisible by anything means it's prime
    return True

# The Rest of the code is the same.

we used power operator(**0.5) to find square root of the number.

Python Program To Find Prime Numbers In A Given Interval

Now let's write a program to find prime numbers in a given interval. example: find all the prime numbers between 2 and 100.

The basic logic of checking the prime number will be the same as above. here we will just change the client code.

def check_prime(number):
    # IF number is less than 2 then return False
    if number < 2:
        return False

    #Find Square root
    root = int(number**0.5) + 1
    for i in range(2,root):
        # Check if number is divisible by i
        if number%i == 0:
            # if divisible then it's not prime
            return False
    # If number is not divisible by anything means it's prime
    return True


l = int(input("Enter Lower Limit : "))
u = int(input("Enter Upper Limit : "))
primes = []
for i in range(l,u):
    if check_prime(i):
        primes.append(i)

print(primes)

Save and run the code. enter lower and upper limits. you should see the similar output.

Output :

Enter Lower Limit : 2
Enter Upper Limit : 20
[2, 3, 5, 7, 11, 13, 17, 19]

That's the wrap for the tutorial to find prime number in python.

Please feel free to comment below if you have any doubts or want to give any suggestions. I will surely reply to you.

Also read about how to reverse a string in python.

Leave a Reply