Python Program To Check Prime Number

Python programming is one of the most popular programming languages that is used in the latest technology. A beginner in any programming languages would have come across initial practice exercises such as identifying prime numbers, even or odd numbers, etc. In this article, we will learn how to write a prime number program in Python to check whether a number entered by the user is a prime number or not. 

To write this program, firstly, we need to understand what a prime number is. A prime number is a natural number that is only divisible by 1 and itself, which means that this number cannot be a product of any other smaller two numbers. For example, 2, 3, 7, 11, 13, 17, etc. are prime numbers.

The program has to check if the number is divisible by any of the numbers lying in between 2 and itself. If it is divisible by any of these numbers, the remainder will be zero, and we can conclude that it is not a prime number. And if the remainder is not zero, then it is a prime number. 

Python Programming Topics 

There are three Python programming topics that one should know to be able to write the prime number program in Python. These are:

1. If…else statement

This is used when there is a need to decide whether to execute a particular set of codes or no. It depends on the condition. If the condition is satisfied, i.e., the test expression is true, then the statements will be executed. If the condition is not satisfied, the statements will not be executed, and it will jump to the ‘else’ section of the code.

if test expression:

Body inside if

else:

         Body inside else

A simple example better explains this:

#To check if the number is positive and print accordingly

num = 5

if num > 0

         print(“Number is Positive)

else

         print(“Number is Negative)

Output: Number is positive

2. For Loop

The For loop is used to iterate over a sequence. So, for each item in the list or set, a set of statements can be executed.

for variable in sequence:

         Body inside for

For example:

sports = [“cricket”, “football”, “tennis”]

for z in sports:

         print(z)

Output: cricket

         football

         tennis

3. Break

The break statement can change the flow of a loop in Python. Usually, a loop repeats over a sequence of codes continuously till the condition is not satisfied or the test expression is false. But sometimes, we may want to stop the current iteration of a loop or maybe the whole loop by checking for one condition. In such cases, a break statement is used.

for variable in sequence:

         if condition:

         break

The loop will be broken once the condition is satisfied.

To understand better with an example:

for var in “mango”:

         if var == “g”:

                     break

                     print(var)

Output: m

         a

         n

Checkout our data science courses to learn more about various data science courses.

upGrad’s Exclusive Data Science Webinar for you –

Watch our Webinar on How to Build Digital & Data Mindset?

Prime Number Program In Python

In this program, we will first ask the user to enter a number. After that, we will check if the number is greater than 1. If it is, we will check if it is divisible by any number between 2 and itself. If it is divisible, then it prints that the number is not a prime number. If it is not divisible, then it prints that the number is a prime number. And if the number is less than 1, then it prints that the number is not a prime number.

The Python program is as follows:

num = int(input("Enter a number: "))

if num > 1:

 for i in range(2, num):

     if (num % i) == 0:

         print(num, "is not a prime number")

         break

 else:

     print(num, "is a prime number")

else:

 print(num, "is not a prime number")

The int() statement is used to convert any number entered by the user into an integer. The range() statement is used so that the value of “i” goes through each number from 2 to the number entered by the user. The print() statement is used to print the value inside the bracket into the output. The user can now check whether any number entered by them is a prime number or no.

Checkout: Top 18 Python Pattern Programs You Must Know About

The Sieve of Eratosthenes Algorithm 

There is an antique set of rules for figuring out high numbers up to a selected size called the Sieve of Eratosthenes. The algorithm generates a list of numbers up to a given limit and then repeatedly notes multiples of each prime until there is no more prime no in Python. The remaining unsigned numbers are all primes. 

The Sieve of Eratosthenes Algorithm is the Python program to check prime number.

def sieve_of_eratosthenes(limit):

    primes = [True] * (limit+1)

    p = 2

    while p**2 <= limit:

        if primes[p]:

            for i in range(p**2, limit+1, p):

                primes[i] = False

        p += 1

    return [i for i in range(2, limit+1) if primes[i]]

A “break” statement in an internal loop is any other optimization technique for verifying primes. There is a vintage set of rules for figuring out top numbers as much as a specific size called the Sieve of Eratosthenes. Instead of repeatedly iterating over all the numbers up to a certain restriction, we may also stop the loop as quickly as we find an issue of the wide variety. A Python Function using the “break” Command

def is_prime(n):

    if n <= 1:

        return False

    for i in range(2, int(n**0.5)+1):

        if n % i == 0:

            return False

            break

    return True

The Difference between “is” and “==” Operators in Python

The “is”; operator determines if variables have an equal price, while the Python "is" operator determines whether variables are a part of the identical memory item. Whether we use the “is” or “==”; the operator would not surely rely whilst evaluating variables to integers or other immutable sorts. On the other hand, the  “is”; operator might also yield surprising outcomes for changeable kinds like dictionaries or lists. It is also a Python program to print prime numbers.

Here is an instance:

a = [1, 2, 3]

b = [1, 2, 3]

print(a == b)   # True

print(a is b)   # False

Recursive Functions to Check Prime Numbers

A recursive function repeatedly calls itself until it hits the main character. An integer’s primeness can be checked using a recursive function. Here is the Prime no program in Python: 

def is_prime(n, i=2):

    if n <= 2:

        return True if n == 2 else False

    if n % i == 0:

        return False

    if i**2 > n:

        return True

    return is_prime(n, i+1)

Miller-Rabin Algorithm 

The Miller-Rabin algorithm, a probabilistic algorithm, is the Python program to find prime number. The algorithm chooses a random witness number and checks that it meets certain conditions. The probability that the algorithm gives a wrong result can be arbitrarily small by choosing enough witnesses. 

Here is a Python implementation of the Miller-Rabin algorithm: 

import random

def is_prime(n, k=5):

    if n <= 3:

        return n == 2 or n == 3

    if n % 2 == 0:

        return False

    # write n-1 as 2^s * d

    s, d = 0, n-1

    while d % 2 == 0:

        s += 1

        d //= 2

    # perform k rounds of testing

    for _ in range(k):

        a = random.randint(2, n-2)

        x = pow(a, d, n)

        if x == 1 or x == n-1:

            continue

        for _ in range(s-1):

            x = pow(x, 2, n)

            if x == n-1:

                break

        else:

            return False

    return True

Conclusion

This article demonstrates how to write a simple program for a prime number in Python language. Using this logic, we can write other basic programs to improve our skills. And we have also learned three programming topics, i.e., if..else statement, for loop, and break. These are basic topics that can be used for more complicated and long programs to execute larger tasks to understand a prime number in Python.

Check out all trending Python tutorial concepts in 2024.

If you are curious about learning data science to be in the front of fast-paced technological advancements, check out upGrad & IIIT-B’s Executive PG Programme in Data Science and upskill yourself for the future.