Contents

## Check if Given Number is Prime

A number is said to be a Prime Number if it has only one and itself as factors.

Based on the definition of a Prime Number, if we can prove that there is no factor in between 1 and the given number, then the given number is a Prime Number.

### Prime Number Program using For Loop

In the following program, we use For loop to iterate from 2 to n, to check if there is any factor for n in that range.

**Python Program**

```
n = int(input('Enter a number : '))
isPrime = True
for i in range(2, n):
if n % i == 0:
isPrime = False
break
if isPrime:
print(n, 'is a Prime Number.')
else:
print(n, 'is not a Prime Number.')
```

Copy**Output #1**

```
Enter a number : 25
25 is not a Prime Number.
```

**Output #2**

```
Enter a number : 11
11 is a Prime Number.
```

**Output #3**

```
Enter a number : 79
79 is a Prime Number.
```

### Efficient Algorithm for Prime Number

If **N** is given number, we can reduce the number of iterations from **1** to **N** by considering the fact that if **i** is not a factor of **N**, then there is no possibility that there would be a factor in the range **(i, N)**.

For example, consider that N is 23, and i is 2. If 2 is not a factor of 23, then there is no integer in the range [23/2, 23) which could be a factor of 23. After that, if 3 is not a factor of 23, then there is no integer in the range [23/3, 23) which could be a factor of 23.

If the number of iterations are reduced, execution time for the program is also reduced, which is a good thing.

**Python Program**

```
n = int(input('Enter a number : '))
i = 2
isPrime = True
while i < (n / i):
if n % i == 0:
isPrime = False
break
i += 1
if isPrime:
print(n, 'is a Prime Number.')
else:
print(n, 'is not a Prime Number.')
```

Copy**Output #1**

```
Enter a number : 9973
9973 is a Prime Number.
```

**Output #**2

```
Enter a number : 87
87 is not a Prime Number.
```