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 listprimes = []
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 listprimes = []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 listprimes = []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.
Factors of 15
Why Compare Different Approaches?
An algorithm is simply a procedure for solving a problem. These approaches have different procedure for solving problems. Notably approach 3 has
Python for Data Structures, Algorithms, and Interviews!_Get a kick start on your career and ace your coding interviews!_www.udemy.com
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 take 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 timeprint(timeit.timeit('approach1(500)', globals=globals(), number=10000))
# Approach 2: Execution timeprint(timeit.timeit('approach2(500)', globals=globals(), number=10000))
# Approach 3: Execution timeprint(timeit.timeit('approach3(500)', globals=globals(), number=10000))
Clearly Approach 3 is the fastest.
Algorithmic Comparison of Different Approaches
An algorithm is simply a procedure or formula for solving a problem. These approaches have different procedures (algorithms) for generating prime numbers. In the previous section, we looked at the time it took to run each algorithm. The problem is the speed depends of the computer you are using. For this section, we will use Big O notation to compare algorithms.
If you are wondering what n is in these different approaches, n is the size of the input. In this case n is the size of the input of some sort.
Approach 1 and 2 are O(n*n)
Approach 3 is O(n*sqrt(n))
Sieve (maybe approach 5) O(n*log(log(n)))
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.