Python Program to Check Prime Number (4 Ways)

In this tutorial, you will learn to write a Python Program to Check Prime Number.

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself.

In other words, a prime number is a number that is only divisible by 1 and itself.

Examples of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and so on.

To understand this program you should have an understanding of the following topics:

1. For Loop

1: By Checking Divisibility by all numbers less than n

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

is_prime = True
for i in range(2, num):
    if num % i == 0:
        is_prime = False
        break

if is_prime:
    print(num, "is a prime number")
else:
    print(num, "is not a prime number")

Output

In this program, we first prompt the user to input a number.

We then declare a boolean variable is_prime and initialize it to True.

We then use a for loop to iterate over the numbers 2 to num-1.

For each number i, we check if num is divisible by i.

If it is, we set is_prime to False and break out of the loop.

If is_prime is still True after the loop finishes, we print out a message indicating that num is prime.

Otherwise, we print out a message indicating that num is not prime.

2: Checking divisibility by all numbers less than the square root of n

import math

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

is_prime = True
for i in range(2, int(math.sqrt(num))+1):
    if num % i == 0:
        is_prime = False
        break

if is_prime:
    print(num, "is a prime number")
else:
    print(num, "is not a prime number")

Output

In this program, we first prompt the user to input a number.

We then import the math module so that we can use the sqrt() function to calculate the square root of num.

We then declare a boolean variable is_prime and initialize it to True.

We then use a for loop to iterate over the number 2 to the square root of num.

For each number i, we check if num is divisible by i.

If it is, we set is_prime to False and break out of the loop.

If is_prime is still True after the loop finishes, we print out a message indicating that num is prime.

Otherwise, we print out a message indicating that num is not prime.

3: Checking divisibility by all odd numbers less than n

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

if num == 2:
    print(num, "is a prime number")
elif num % 2 == 0:
    print(num, "is not a prime number")
else:
    is_prime = True
    for i in range(3, num, 2):
        if num % i == 0:
            is_prime = False
            break

    if is_prime:
        print(num, "is a prime number")
    else:
        print(num, "is not a prime number")

Output

In this program, we first check if the number is 2, which is the only even prime number.

If it is 2, we print that it is a prime number.

If it is not 2 but is even, we print that it is not a prime number.

If the number is odd, we set a flag variable is_prime to True.

We then loop through all odd numbers from 3 to num-1, checking if num is divisible by each number.

If it is, we set is_prime to False and break out of the loop.

If we loop through all odd numbers without finding one that divides num, then is_prime will still be True, indicating that num is a prime number.

4: By Using the Sieve of Eratosthenes algorithm

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

sieve = [True] * (n+1)
sieve[0] = False
sieve[1] = False

for i in range(2, int(n**0.5)+1):
    if sieve[i]:
        for j in range(i*i, n+1, i):
            sieve[j] = False

if sieve[n]:
    print(n, "is a prime number")
else:
    print(n, "is not a prime number")

Output

In this program, we first create a list called sieve with n+1 elements, all initially set to True.

We then set the first two elements (sieve[0] and sieve[1]) to False, since 0 and 1 are not prime.

We then loop through all the numbers from 2 to the square root of n, checking if each number is prime (i.e., if sieve[i] is True).

If it is, we mark all its multiples as not prime by setting sieve[j] to False, where j is a multiple of i.

Finally, we check whether n is prime by checking the value of sieve[n].

If it is True, we print that n is a prime number.

Otherwise, we print that n is not a prime number.