Python Program to Check Prime Number

by

In mathematics prime numbers refer to a positive integer greater than 1 that can only be evenly divided by 1 and itself.

This means that a prime number has no other positive integer divisors besides these two. For instance, the example of prime numbers are 2, 3, 5, 7, 11, 13, and so on. These numbers are unique because they cannot be divided by any other number except for 1 and themselves.

Prime numbers have major roles in many fields, including number theory, cryptography, and computer science.
Prime numbers play a vital role in securing online transactions through public key cryptography algorithms, as well as ensuring the integrity of data through hashing functions.

In this example, you will learn to write a Python program to check whether a given input number is prime or not.

Example 1: Using a For loop to check divisibility

# Python program to check if a number is prime or not

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

# prime numbers are greater than 1
if num > 1:
    # check for factors
    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")

# if input number is less than or equal to 1, it is not prime
else:
    print(num, "is not a prime number")

Output

$ Enter a number: 17
17 is a prime number

Using recursion to check for divisibility of a prime number


def is_prime(num, divisor=2):
    # base case 1: input number is less than or equal to 1
    if num <= 1:
        return False

    # base case 2: input number is divisible by divisor
    if num == divisor:
        return True

    # recursive case: check if num is divisible by divisor, and call function with incremented divisor
    if num % divisor == 0:
        return False
    else:
        return is_prime(num, divisor+1)

# test the function
print(is_prime(17))    # True
print(is_prime(4))     # False
print(is_prime(1))     # False

Output

True
False
False

To improve the efficiency of the prime number checking algorithm, we can reduce the time complexity by only examining numbers up to the square root of the given number. This is because any factor larger than the square root must have a corresponding factor that is less than the square root. Here's an example of a Python program that uses the square root optimization to check if a given number is prime or not.
import math

def is_prime(num):
    # prime numbers are greater than 1
    if num > 1:
        # check for factors up to the square root of the input number
        for i in range(2, int(math.sqrt(num))+1):
            if (num % i) == 0:
                return False
        else:
            return True

    # if input number is less than or equal to 1, it is not prime
    else:
        return False

# test the function
print(is_prime(17))    # True
print(is_prime(4))     # False
print(is_prime(1))     # False

Output

True
False
False

In conclusion, we can determine if a given input number is prime or not by checking its factors up to the square root of the number, which reduces the time complexity and has important implications in cryptography, computer science, and other fields.

Leave a Comment