The Indivisibles

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L5
Asked in
Rackspace Technology

Problem

Given a positive integer n, return all prime numbers strictly less than n in ascending order. Return an empty list when n <= 2.

Numbers that yield only to themselves.

Example 1

Input:

n = 10

Output:

[2,3,5,7]

Example 2

Input:

n = 2

Output:

[]

Worked solution and explanation

Why this problem exists in real interviews

This tests the Sieve of Eratosthenes, the most efficient algorithm for generating all primes below a threshold. It probes array manipulation, boolean masking, and understanding of the sieve's mathematical basis.

Break down the requirements

Step 1: Create a boolean sieve array

Index i represents whether i is prime. Initialize all to True, then set 0 and 1 to False.

Step 2: Mark multiples of each prime

For each number p from 2 to sqrt(n), if sieve[p] is True, mark p*p, p*p+p, ... as False.

Step 3: Collect remaining True indices

These are the primes below n.

The solution

Sieve of Eratosthenes
def primes_below(n: int) -> list:
    if n < 2:
        return []
    sieve = [True] * n
    sieve[0] = False
    sieve[1] = False
    p = 2
    while p * p < n:
        if sieve[p]:
            multiple = p * p
            while multiple < n:
                sieve[multiple] = False
                multiple += p
        p += 1
    result = []
    for i in range(n):
        if sieve[i]:
            result.append(i)
    return result

Common follow-up questions