Prime Numbers using Python
Write a program to generate a list of all prime numbers less than 20.
Before starting it is important to note what a prime number is.
- A prime number has to be a positive integer
- Divisible by exactly 2 integers (1 and itself)
- 1 is not a prime number
While there are many different ways to solve this problem, here are a few different approaches.
Approach 1: For Loops
# Initialize a list
primes = []for possiblePrime in range(2, 21):
# Assume number is prime until shown it is not.
isPrime = True
for num in range(2, possiblePrime):
if possiblePrime % num == 0:
isPrime = False
if isPrime:
primes.append(possiblePrime)
If you look at the inner for loop enclosed in the red rectangle below, notice that as soon isPrime
is False, it is inefficient to keep on iterating. It would be more efficient to exit out of the loop.
Approach 2: For Loops with Break
Approach 2 is more efficient than approach 1 because as soon as you find a given number isn’t a prime number you can exit out of loop using break
.
# Initialize a list
primes = []
for possiblePrime in range(2, 21):
# Assume number is prime until shown it is not.
isPrime = True
for num in range(2, possiblePrime):
if possiblePrime % num == 0:
isPrime = False
break
if isPrime:
primes.append(possiblePrime)
Approach 2 is much more efficient than approach 1. For example, if you look at the case when possiblePrime = 15
, notice that there is much less iteration in approach 2.
Approach 3: For Loop, Break, and Square Root
Approach 2 benefited from not doing unnecessary iterations in the inner for loop. Approach 3 is similar except the inner range function. Notice that the inner range function is now range(2, int(possiblePrime ** 0.5) + 1)
.
# Initialize a list
primes = []
for possiblePrime in range(2, 21):
# Assume number is prime until shown it is not.
isPrime = True
for num in range(2, int(possiblePrime ** 0.5) + 1):
if possiblePrime % num == 0:
isPrime = False
break
if isPrime:
primes.append(possiblePrime)
To explain why this approach works, it is important to note a few things. A composite number is a positive number greater than 1 that is not prime (which has factors other than 1 and itself). Every composite number has a factor less than or equal to its square root (proof here). For example, in the image of the factors of 15 below, notice that the factors in red are just the reverses of the green factors. In other words, by the commutative property of multiplication 3 x 5 = 5 x 3. You just need to include the green pairs to be sure that you have all the factors.
Time Comparison of Different Approaches
Certain methods to generate prime numbers are more efficient. To show this, let’s study time the performance difference between the approaches generating prime numbers up to a given number.
Approach 1: For Loops
def approach1(givenNumber): # Initialize a list
primes = []
for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not.
isPrime = True
for num in range(2, possiblePrime):
if possiblePrime % num == 0:
isPrime = False if isPrime:
primes.append(possiblePrime)
return(primes)
Approach 2: For Loops with Break
def approach2(givenNumber): # Initialize a list
primes = []
for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not.
isPrime = True
for num in range(2, possiblePrime):
if possiblePrime % num == 0:
isPrime = False
break if isPrime:
primes.append(possiblePrime)
return(primes)
Approach 3: For Loop, Break, and Square Root
def approach3(givenNumber):
# Initialize a list
primes = []
for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not.
isPrime = True
for num in range(2, int(possiblePrime ** 0.5) + 1):
if possiblePrime % num == 0:
isPrime = False
break if isPrime:
primes.append(possiblePrime)
return(primes)
The performance difference can be measured using the the timeit
library which allows you to time your Python code. In this case, we are measuring the time it takes to find prime numbers up to 500 for each approach. The code below runs the code for each approach 10000 times and outputs the overall time it took in seconds.
import timeit# Approach 1: Execution time
print(timeit.timeit('approach1(500)', globals=globals(), number=10000))# Approach 2: Execution time
print(timeit.timeit('approach2(500)', globals=globals(), number=10000))# Approach 3: Execution time
print(timeit.timeit('approach3(500)', globals=globals(), number=10000))
Concluding Remarks
The three approaches are definitely not the only ways to calculate prime numbers, but hopefully the various ways of identifying prime numbers helped you. Prime numbers are important in number theory and cryptographic methods like the rsa algorithm. As always, the code in the post is also available on my github (approach code, time comparison). If you any questions or thoughts on the tutorial, feel free to reach out in the comments below or through Twitter. My next tutorial goes over Using Python to Detect Anagrams. If you want to learn how to utilize the Pandas, Matplotlib, or Seaborn libraries, please consider taking my Python for Data Visualization LinkedIn Learning course. Here is a free preview video.