How to Test for Prime Numbers in Python | Python Program to Check if Number is Prime or Not

One of the best things that you can perform with python is checking the given number is prime or not. The prime numbers concept is very standard and remembered from primary math class. If you want to learn what is a prime number and how to test the number is prime or not in python check out the following modules without any fail.

What is a Prime Number?
How to Test for Prime Numbers in Python?
Python Program for prime number
Python program to check whether a number is Prime or not
Optimized Method

Explore more instances related to python concepts from Python Programs and get promoted from beginner to professional programmer level in Python Programming Language.

What is a Prime Number?

A prime number is any whole number (it must be greater than 1), whose only factors are 1 and itself, determining it can’t evenly be divided by any number (apart from 1 and itself, of course). Prime numbers include 2, 3, 5, 7, 11, 13, and so on until infinity.

How to Test for Prime Numbers in Python?

The best way to resolve this issue is to repeat through all the numbers beginning from 2 to (N/2) with the help of a for loop and for every number check if it divides N. If we discover any number that divides, we return false. If we did not find any number between 2 and N/2 which divides N then it implies that N is prime and we will return True.

To grasp this concept, you need to get a good grip on the python programming concepts like Python if…else Statement, Python for Loop, and Python break and continue.

In Python, we can test for prime numbers quite efficiently using the following code:

if num > 1:

for i in range(2,num):
 if (num % i) == 0:
 print(num,"is not a prime number")
 print(i,"times",num//i,"is",num)
 break
 else:
 print(num,"is a prime number")
 
else:
 print(num,"is not a prime number")

First, the code monitors the number is greater than 1 (anything less than one can’t be a prime number because it isn’t whole). Then it checks to see if the number is divisible by any number between 2 and the number you’re checking. If it is divisible, then you’ll see from the output that the number is not prime. If it isn’t divisible by any of those numbers, then the message on the output will read “[num] is not a prime number.”

Do Check:

Python Program for prime number

Let us perform the logic in python by using the defined function. Firstly, you can observe the algorithm for the prime number python program below:

Algorithm:

Initialize a for loop starting from 2 ending at the integer value of the floor of the square root of the number
Check if the number is divisible by 2
Repeat till the square root of the number is checked for.
If the number is divisible by any of the numbers, the number is not prime
Else, it is a prime number

Code:

import math

def primeCheck(x):
sta = 1
for i in range(2,int(math.sqrt(x))+1): # range[2,sqrt(num)]
if(x%i==0):
sta=0
print("Not Prime")
break
else:
continue
if(sta==1):
print("Prime")
return sta

num = int(input("Enter the number: "))
ret = primeCheck(num)

Output:

Enter the number: 117
Not prime

Python program to check whether a number is Prime or not

# Python program to check if
# given number is prime or not
 
num = 11
 
# If given number is greater than 1
if num > 1:
 
    # Iterate from 2 to n / 2
    for i in range(2, int(num/2)+1):
 
        # If num is divisible by any number between
        # 2 and n / 2, it is not prime
        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")

Optimized Method

There are several ways to optimize the prime number program in Python:

Rather than checking till n, we can check till √n because a larger factor of n needs to be a multiple of a smaller factor that has been already checked.
The algorithm can be refined more by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = ?1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1.

Example Code:

def isPrime(n) :
if (n <= 1) :
return False
if (n <= 3) :
return True
if (n % 2 == 0 or n % 3 == 0) :
return False
i = 5
while(i * i <= n) :
if (n % i == 0 or n % (i + 2) == 0) :
return False
i = i + 6
return True
if (isPrime(11)) :
print(" true")
else :
print(" false")
if(isPrime(15)) :
print(" true")
else :
print(" false")