Python Interview: Prime Numbers

Write a program to make a list of all prime numbers less than 20.

Before starting it is important to note what a prime number is.

1. A prime number has to be a positive integer
2. Divisible by exactly 2 integers (1 and itself)
3. 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.

Factors of 15

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 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))

Clearly Approach 3 is the fastest.

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.

This article originally appeared on my medium blog