A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. An another way to define prime number is: a prime number is a natural number that has no positive divisors other than 1 and itself. Following are some prime numbers:

2,3,5,11,17……

We’ll write a program to check whether the given number is prime or not.

Method 1

To check whether a given number is prime or not, we need to check whether the number has a positive divisor or not other than 1. To check for a given number n, it is sufficient to check whether n is divisible between n and n/2. This is because it is not possible for n to have a divisor greater than n/2.

# Python program to check if a given number is prime or not 
number = int(input('Please input a number:'))
  
# Check if the number is positive number greater than 1 
if number > 1: 
      
   # Iterate from 2 to n / 2  
   for i in range(2, number//2): 

       # If number is divisible by any number between  
       # 2 and n / 2, it is not prime  
       if (number % i) == 0: 
           print(number, "is not a prime number") 
           break
   else: 
       print(number, "is a prime number") 
  
else: 
   print(number, "is not a prime number")

Output

Please input a number:13
13 is a prime number

Method 2 (Optimized method)

The optimized solution is based on the fact that all prime numbers are of the form 6k±1 with the exception of 2 and 3. All integers can be expressed in the form of 6k+i for some integer k and i=0,1,2,3 or 4. So we have following representation of numbers:

(6k+0), (6k+1), (6k+2), (6k+3) and (6k+4)

Here, (6k+0), (6k+2) and (6k+4) are divisible by 2 and (6k+3) is divisible by 3.

So the optimized solution is to check if the number n is divisible by 2 or 3 and check for the number of the form 6k+1.

# Python3 - Optimized program to check 
# if a number is prime or not
  
def isPrime(number): 
  
    # check if number is less than equal to 1 
    if (number <= 1): 
        return False
    # check if number is less than equal to 3
    if (number <= 3): 
        return True
  
    # If number is divisible by 2 or 3 it is not prime 
    if (number % 2 == 0 or number % 3 == 0): 
        return False
  
    i = 5
    while(i * i <= number): 
        if (number % i == 0 or number % (i + 2) == 0): 
            return False
        i = i + 6
  
    return True

num = int(input('Please provide number to check:'))
if (isPrime(num)):
    print(num, "is a prime number")
else:
    print(num, "is not a prime number")

Output

Please provide number to check:11
11 is a prime number