Python Program To Check a Number Is Prime Number or Not?

prime number program in python

Hey Shouters!! Today we will learn about the prime number program in python using two different methods.

If you are a beginner and do not know how to write a python program. Please check Introduction To Python and How to Install a Python IDE.

So, first we will define what is a prime number and the logic of the problem.

What is a Prime Number-

A prime number is a natural number which is only divisible by 1 and the number itself. This means that there is no divisor of the number other than 1 and that number. Example of first first few prime numbers are {2, 3, 5, 7, 11, ….}.

Logic of the Program-

  1. First we will take the input from the user.
  2. We will iterate the loop from 2 to the number/2 to check if the number is divisible by any of the number in the range.
  3. If the number is divisible by any number that means it has a divisor and so the number is not a prime number.
  4. But, if the number is not divisible by any number that means it is a prime number.
  5. We will print the output accordingly.

1. Iterative Method for Prime Number Program in Python-

In this method, we will first take the input from the user and will check whether it is greater than 1 or not.

If number is greater than 1 then we will iterate the loop from 2 to n/2. and will check the divisibility of the number in the loop.

And check if it is divisible the number is not a prime number and if not divisible, it is a prime number.

Output:

Example 1- Enter the number 11

11 is a prime number

Example 2- Enter the number 18

18 is not a prime number

2. Optimized Method for Python Program in Python-

  1. Rather than checking till n, we will check till √n because a larger factor of n must be a multiple of smaller factor that has been already checked.
    2. The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = ?1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1.

Output:

Example 1- 11 is a prime number

Example 2- 18 is not a prime number

Recommended Posts-

  1. Introduction to Python and Environment Setup
  2. Python Program to Check a Year is Leap Year or Not
  3. Python Program to Check a Palindrome Number
  4. Word Guessing Game in Python
  5. Python Program to convert decimal to binary number

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami