How to Find Prime Numbers in Python
Last updated on Jul 13,2022 225.1K Views
2 / 11 Blog from Python Programs
A prime number is a natural number greater than 1 and it does not have any divisor other than 1 and itself. You can write a code in Python that will help you find all the prime numbers. In this article, we will see how to write a prime number program in Python in the following sequence:
- What is a Prime number?
- Python Program to check Prime Number
- Optimized Method
Let’s get started.
What is a Prime Number?
A positive integer greater than 1 which does not have other factors except 1 and the number itself is called a prime number. The numbers 2, 3, 5, 7, etc. are prime numbers as they do not have any other factors. To find a prime number in Python, you have to iterate the value from start to end using a for loop and for every number, if it is greater than 1, check if it divides n. If we find any other number which divides, print that value.
Find out our Python Training in Top Cities/Countries
India | USA | Other Cities/Countries |
Bangalore | New York | UK |
Hyderabad | Chicago | London |
Delhi | Atlanta | Canada |
Chennai | Houston | Toronto |
Mumbai | Los Angeles | Australia |
Pune | Boston | UAE |
Kolkata | Miami | Dubai |
Ahmedabad | San Francisco | Philippines |
A prime number is always positive and it will be checked at the beginning of the program. Here, you will divide the input number by all the numbers to see whether there are any positive divisors other than 1 and number itself. If any divisor is found then we display that the “number is not a prime number” else we display that the “number is a prime number”.
Python program:
num = 13 if num > 1: for i in range[2, num//2]: if [num % i] == 0: print[num, "is not a prime number"] break else: print[num, "is a prime number"] else: print[num, "is not a prime number"]
Output: 13 is a prime number
Optimized Method
There are different ways to optimize the prime number program in Python:
- Instead of checking till n, we can check till √n because a larger factor of n must be a multiple of smaller factor that has been already checked.
- 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.
Example:
def isPrime[n] : if [n <= 1] : return False if [n <= 3] : return True if [n % 2 == 0 or n % 3 == 0] : return False i = 5 while[i * i <= n] : if [n % i == 0 or n % [i + 2] == 0] : return False i = i + 6 return True if [isPrime[11]] : print[" true"] else : print[" false"] if[isPrime[15]] : print[" true"] else : print[" false"]
With this, we have come to the end of our article. I hope you understood how to write a prime number program in Python Programming.
To get in-depth knowledge of Python along with its various applications, you can enroll for live Python Certification Training with 24/7 support and lifetime access.
Got a question for us? Please mention it in the comments section of this “Prime Number Program in Python” blog and we will get back to you as soon as possible or join our Master Python programming course today.
Stay ahead of the curve in technology with This Post Graduate Program in AI and Machine Learning in partnership with E&ICT Academy, National Institute of Technology, Warangal. This Artificial Intelligence Course is curated to deliver the best results.
Upcoming Batches For Python Certification Training Course
Python Certification Training Course | Class Starts on 15th October,2022 15th October SAT&SUN [Weekend Batch] | View Details |
Python Certification Training Course | Class Starts on 12th November,2022 12th November SAT&SUN [Weekend Batch] | View Details |
Recommended videos for you
Know The Science Behind Product Recommendation With R Programming
Watch Now
Introduction to Business Analytics with R
Watch Now
3 Scenarios Where Predictive Analytics is a Must
Watch Now
Python Loops – While, For and Nested Loops in Python Programming
Watch Now
Sentiment Analysis In Retail Domain
Watch Now
Business Analytics Decision Tree in R
Watch Now
The Whys and Hows of Predictive Modelling-I
Watch Now
Python Numpy Tutorial – Arrays In Python
Watch Now
Python Programming – Learn Python Programming From Scratch
Watch Now
Web Scraping And Analytics With Python
Watch Now
Python Tutorial – All You Need To Know In Python Programming
Watch Now
Android Development : Using Android 5.0 Lollipop
Watch Now
The Whys and Hows of Predictive Modeling-II
Watch Now
Python Classes – Python Programming Tutorial
Watch Now
Application of Clustering in Data Science Using Real-Time Examples
Watch Now
Python List, Tuple, String, Set And Dictonary – Python Sequences
Watch Now
Recommended blogs for you
Statistics for Machine Learning: A Beginner’s Guide
Read Article
A Quick Guide To Learn What’s New In Python 3.8
Read Article
Tkinter Tutorial For Beginners | GUI Programming Using Tkinter In Python
Read Article
What do you know about Business Analytics With R?
Read Article
Threading In Python: Learn How To Work With Threads In Python
Read Article
How To Become A Machine Learning Engineer? – Learning Path
Read Article
KNN Algorithm: A Practical Implementation Of KNN Algorithm In R
Read Article
Implementing K-means Clustering to Classify Bank Customer Using R
Read Article
Support Vector Machine In R: Using SVM To Predict Heart Diseases
Read Article
What is NumPy in Python – Introduction to NumPy – NumPy Tutorial
Read Article
Why Python Programming Language Is a Must Have Skill?
Read Article
PyGame Tutorial – Game Development Using PyGame In Python
Read Article
Top Deep Learning Interview Questions You Must Know in 2022
Read Article