Progress

Python program to check prime number: Optimized Approach

Python program to check prime number: Optimized Approach

This is the most popular question for beginners of all language. Prime numbers are mostly a part of programming interviews with a twist. It is important to know the optimized Python program to check the prime number.

Before going to write a Python program to check prime numbers we need to know what are prime and composite numbers.

Prime numbers are those numbers which are only divisible by 1 and itself. Example of prime numbers is 2, 3, 5, 7, 11, 13 and so on.

Composite numbers are those numbers which are not prime numbers. It means those integers which can be formed by multiplying two integers. Examples of Composite numbers is 4 (2*2), 6 (3*2), 8 (2*4), 9 (3*3) and so on.

Note that 1 is neither prime nor composite number.

Python Program: Check Prime Number

This is a general solution to check if a number is prime or not.

Copy
n = 18

#n = int(input("Enter the number: "))

for i in range(2, n):
    if(n%i==0):
        print("{} is NOT a prime number".format(n))
        break
else:
    print("{} is a prime number".format(n))
Output
18 is NOT a prime number

The logic of the program is simple, we loop through numbers from 2 to n and check if any number between them divides n completely.

If we find any factor of n then it is NOT a prime number.

The else statement with for loop can be new for non-Python programmers. It depends on if statement inside for loop. The else statement runs only when the, if statement inside for loop does not, terminates using break.

In simple words else statement execute only when the for loop complete without break.

Optimized Python program find prime numbers

This is a general solution to find prime numbers in any language.

Copy
num = 18

#num = int(input("Enter the number: "))
for i in range(2, int(num**0.5)+1):
    if(num%i==0):
        print("{} is NOT a prime number".format(num))
        break
else:
    print("{} is a prime number".format(num))
Output
18 is NOT a prime number

This solution is based on the fact that a composite number has a prime factor less than or equal to its square root. This might be confusing so I will clarify it by examples.

Example:

  • 10: Square root = 3.16 and it has factor 2 (less than 3.16)
  • 15: Square root = 3.87 and it has factor 3 (less than 3.87)

Code Explanation:

We loop through 2 to the square root of the number (inclusive) and find if it has any factors. If it has no factors then for loop completes without break and else prints that it is a prime number.

These were some of the most popular Python programs to find prime numbers. If have any better solution or any query then feel free to comment.

Share the Post ;)

Related Posts