Python Program - Check if Given Number is Prime

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.