## 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.')
```

**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.')
```

**Output #1**

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

**Output #**2

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

## Related Tutorials

- How to Get Number of Elements in Pandas DataFrame?
- Python Program to Add Two Numbers
- How to Swap Two Numbers in Python?
- Reverse a Number in Python
- Python – Check if Number is Armstrong
- Numpy sqrt() – Find Square Root of Numbers
- Python – Smallest of Three Numbers
- Python – Sum of First N Natural Numbers
- Python Complex Number – Initialize, Access
- Python – Largest of Three Numbers