The Number Screen

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
L3
Asked in
Rackspace Technology

Problem

Return all prime integers strictly less than n, in ascending order. For n <= 2, return an empty list. Do not use any math libraries; implement divisibility checks yourself.

Some numbers make the cut. Most do not.

Example

Input:

n = 10

Output:

[2,3,5,7]

Worked solution and explanation

Why this problem exists in real interviews

Prime sieving is the classic stand in for whether you remember the sqrt optimization, can implement the Sieve of Eratosthenes from scratch, and reason about the difference between strict and non strict upper bounds. Interviewers care less about the specific algorithm and more about how you justify the complexity.

Break down the requirements

Step 1: Handle the small n base case

For n <= 2 return [] immediately. The smallest prime is 2 and the spec says strictly less than n, so n == 2 yields no primes. Stating this base case up front prevents off by one errors in the sieve loop.

Step 2: Build a boolean sieve of length n

Mark is_prime = [True] * n, set indices 0 and 1 to False, then for each i from 2 up to sqrt(n) cross off multiples starting at i*i. Starting at i*i not 2*i skips work already done by smaller primes.

Step 3: Collect indices that survived

Return [i for i in range(2, n) if is_prime[i]]. The strict range(2, n) matches the spec's strict less than rule without an extra comparison.

The solution

Sieve of Eratosthenes with sqrt cutoff
def primes_less_than(n: int) -> list[int]:
    if n <= 2:
        return []
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i < n:
        if is_prime[i]:
            for multiple in range(i * i, n, i):
                is_prime[multiple] = False
        i += 1
    return [i for i in range(2, n) if is_prime[i]]

Common follow-up questions