• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Basics / Check For Prime Number in Python

Check For Prime Number in Python

Author: Aditya Raj
Last Updated: January 9, 2022

Prime numbers are those numbers that have only two factors i.e. 1 and the number itself. In this article, we will discuss two ways to check for a prime number in python.

What is a prime number?

Prime numbers are those positive integers greater than one that has only two factors. The examples of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, etc.

Here, 

  • 2 has only two factors i.e. 1 and 2.
  • 3 has only two factors i.e. 1 and 3.
  • 5 has only two factors i.e. 1 and 5.

You can observe that all other numbers also have only two factors. 

Check For Prime Number in Python

For checking if a number is prime or not, we just have to make sure that all the numbers greater than 1 and less than the number itself should not be a factor of the number. For this, we will define a function isPrime() that takes a number N as input. Then it checks whether any number between 2 and N-1 is a factor of N or not using a for loop. If a factor is present, it returns False stating that the input number N is not a prime number. Otherwise, it returns True.

def isPrime(N):
    for number in range(2, N):
        if N % number == 0:
            return False
    return True


input_number = 23
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))
input_number = 126
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))

Output:

23 is a Prime number:True
126 is a Prime number:False

In the above example, we have checked every number from 2 to N-1 to see if it is a factor of N or not. We can optimize this process by checking numbers till N/2 instead of N-1. This is so because the only factor of N greater than N/2 is the number N itself. So, we will check for factors in numbers only till N/2. Additionally, we can also check if a number is even or not. If a number greater than 2 is even, it will never be a prime number. We can define an improved isPrime() function using these concepts as given below.

def isPrime(N):
    for number in range(2, N//2):
        if N % number == 0:
            return False
    return True


input_number = 23
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))
input_number = 126
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))

Output:

23 is a Prime number:True
126 is a Prime number:False

We can again optimize the above program using simple logic. You can observe that factors of a number always occur in pairs. For a number N, the factors can be paired as (1, N), (2, N/2), (3, N/3), (4, N/4) till (N1/2, N1/2). So, for checking for factors, we can check only till N1/2 instead of N/2. 

For example, if we are given a number 100, all the factors can be paired as (1,100), (2,50),(4,25), (5,20), and (10,10). Here, if 100 is divisible by 2, it must be divisible by 50, if 100 is divisible by 4, it must be divisible by 25. We don’t need to explicitly check both the numbers in a pair to check if a number is a factor or not. So, To check for prime number, We can simply check for a factor till N1/2 instead of N/2 using a while loop. If a factor is not present between 2 and N1/2, the number must be a prime number. Using this logic, we can modify the isPrime() function used in the above example as follows.

def isPrime(N):
    count = 2
    while count ** 2 <= N:
        if N % count == 0:
            return False
        count = count + 1
    return True


input_number = 23
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))
input_number = 126
output = isPrime(input_number)
print("{} is a Prime number:{}".format(input_number, output))

Output:

23 is a Prime number:True
126 is a Prime number:False

Conclusion

In this article, we have discussed three ways to check for a prime number in python. To learn more about numbers, you can read this article on complex numbers in python. You might also like this article on decimal numbers in Python.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: Basics Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup bitly Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary – How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehensions in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Pandas Append Row to DataFrame
  • Convert String to DataFrame in Python
  • Pandas DataFrame to List in Python
  • Solved: Dataframe Constructor Not Properly Called Error in Pandas
  • Overwrite a File in Python

Copyright © 2012–2023 · PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us