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
```