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.*