**Prime Number is a natural number greater than 1, which is divisible by 1 and itself**. For example, 2, 5, 3, 7 are all prime numbers. A composite number is a number greater than 1, that is divisible by a number other than 1 and itself. This article discusses several approaches to check if a number is prime or not.

Let us consider the example given below. A variable** num** is declared which takes input from the user. Another variable** flag** is initialized to 0. Numbers less than or equal to 1 are not prime numbers. The if statement checks if the number is greater than 1. If the condition is True the control of the program executes the **for loop**.

The for loop iterates for a range of** 2 to num-1.** In each iteration, the program checks if the number **num** is divisible by any number in that range. If a factor is found in that range number is not prime and the variable **flag is set to 1.** Otherwise, if the value of the variable **flag remains 0,** this indicates a number **num** is a prime number.

**The time Complexity for the below program is O(N).**

```
num = int(input("Enter a number: "))
flag = 0
if num > 1:
for i in range(2, num):
if num % i == 0:
flag = 1
print(num, " is not a Prime Number")
break
if flag == 0:
print(num, "is a Prime Number")
else:
print(num, " is not a Prime Number")
```

The above program is checked for multiple test cases, which returns the output as

```
Enter a number: 7
7 is a Prime Number
Enter a number: 14
14 is not a Prime Number
Enter a number: -9
-9 is not a Prime Number
```

**We know that every composite number has at least one prime factor less than or equal to the square root of the number itself.** So, instead of checking till the number(num), we can check till (sqrt(num)). This reduces the time complexity to **O( sqrt(num)).**

```
import math
num = int(input("Enter a number: "))
flag = 0
if num > 1:
for i in range(2, int(math.sqrt(num))+ 1):
if num % i == 0:
flag = 1
print(num, " is not a Prime Number")
break
if flag == 0:
print(num, "is a Prime Number")
else:
print(num, " is not a Prime Number")
```

Output

```
Enter a number: 7
7 is a Prime Number
```

This algorithm can be improved further. All the prime numbers except 2 and 3 are of the form 6k ± 1 where k is a positive integer greater than 0. So first, we will check if the number is divisible by 2 or 3 or the number is less than or equal to 1. If the condition is True number is not a Prime number.

Otherwise, we will check if the number is divisible by any of the prime numbers less than** sqrt(num)**. If the condition is **True** number is not prime else a number is a **Prime number**.

```
import math
num = int(input("Enter a number: "))
if (num%2 == 0) or (num%3 == 0) or (num <= 1):
print(num, "is not a Prime Number")
else:
flag = 0
i = 5 # initializing i to 6k-1, where k =1
while( i <= int(math.sqrt(num))):
# checking if num is divisible by 6k ± 1
if (num % i == 0) or (num % (i+2) == 0):
flag = 1
print(num, " is not a Prime Number")
break
i = i + 6 # incrementing i in each time by 6 steps
if flag == 0:
print(num, "is a Prime Number")
```

The above code is check for multiple test cases given below which returns the output as

```
Enter a number: 9
9 is not a Prime Number
Enter a number: 7
7 is a Prime Number
Enter a number: -43
-43 is not a Prime Number
```

Let us consider an example, where we find all the prime numbers till N = 15 . We initialize an empty list** list_prime** to store all the prime numbers. A for loop iterates over the range of 2 and 15. In each iteration it checks if the number is prime by using another nested **for loop**.

If the number is not prime, the break statement breaks the loop. Otherwise, the else block appends the number to **list_prime.**

```
N = 15
list_prime = []
for num in range(2, N+1):
if num > 1:
for i in range(2, num):
if num % i == 0:
break
else:
list_prime.append(num)
print("list_prime: ", list_prime)
```

Output

`list_prime: [2, 3, 5, 7, 11, 13]`

**Sieve of Eratosthenes is the most efficient algorithm to generate all the prime numbers for a given range.** Let us consider a number n, We have to find all the prime numbers from 2 to n.

- Create a list from 2 to n with the value True. The algorithm starts with the smallest prime number 2. The variable p is initialized to 2, p = 2.
- Mark all the multiples of p from 2p, 3p, 4p....... n as False(This indicates all the numbers marked with False are not prime).
- The program then finds the smallest unmarked number greater than p and initializes the variable p with that number.
- If there is no such number, then the process stops. Otherwise, it repeats the execution from step 2.

It is sufficient to mark the numbers in step 2 starting from p2 (p*p), as all the smaller multiples of p will have already been marked at that point.

Consider the following example, a variable **n** is initialized to value 15. The **list_1** of length (n +1) is created and is initialized with **True. **The variable **p** in initialized to 2. The while loop checks if **p** is prime(if list_1[p] is not change to Flase, then p is prime) and marks all the multiples of p to value** False. **The value of p is incremented by 1 in each iteration.

Another for loop traverses the **list_1** from 2 to n+1. If the value at that index is True, The index number is appended to list** list_prime.**

```
n =15
list_1 = [True for i in range(n+1)]
p = 2
while (p * p <= n):
# If list_1[p] is not changed to False,
# then it is a prime
if (list_1[p] == True):
# All the multiples of p are updated
for i in range(p * p, n+1, p):
list_1[i] = False
p += 1
list_prime =[]
for p in range(2, n+1):
if list_1[p] == True:
list_prime.append(p)
print("list_prime: ", list_prime)
```

The above code returns the output as

`list_prime: [2, 3, 5, 7, 11, 13]`

- How to check if a number is negative in python?
- How to get the last element of a list in python?
- How to get absolute value in Python?
- How to check the type of a variable in python?
- How to shuffle a list in python?
- How to remove a key from a dictionary python?
- How to Typecast in Python?
- How to remove duplicates from a list?