Python Programming (138 Blogs) Become a Certified Professional
AWS Global Infrastructure

Data Science

Topics Covered
  • Business Analytics with R (32 Blogs)
  • Data Science (26 Blogs)
  • Mastering Python (92 Blogs)
  • Decision Tree Modeling Using R (1 Blogs)
SEE MORE

How to Find Prime Numbers in Python

Last updated on Jan 03,2023 261.9K 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.

Python Full Course – Learn Python in 12 Hours | Python Tutorial For Beginners | Edureka

This Edureka Python Full Course helps you to became a master in basic and advanced Python Programming Concepts.

In this article, we will see how to write a prime number program in Python in the following sequence:

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

IndiaUSAOther Cities/Countries
BangaloreNew YorkUK
HyderabadChicagoLondon
DelhiAtlantaCanada
ChennaiHoustonToronto
MumbaiLos AngelesAustralia
PuneBostonUAE
KolkataMiamiDubai
AhmedabadSan FranciscoPhilippines

Python Program to Check Prime Number

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
Course NameDate
Python Certification Training Course

Class Starts on 28th January,2023

28th January

SAT&SUN (Weekend Batch)
View Details
Python Certification Training Course

Class Starts on 25th February,2023

25th February

SAT&SUN (Weekend Batch)
View Details
Python Certification Training Course

Class Starts on 25th March,2023

25th March

SAT&SUN (Weekend Batch)
View Details
Comments
0 Comments

Join the discussion

Browse Categories

webinar REGISTER FOR FREE WEBINAR
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP

Subscribe to our Newsletter, and get personalized recommendations.

image not found!
image not found!

How to Find Prime Numbers in Python

edureka.co