โ† SAP questions

Print all prime numbers smaller than N

Filed under SAP

Free read 1 of 3

If n <= 2, return an empty list immediately since the smallest prime number is 2.

The question

Given an integer `n`, return a list of all prime numbers strictly smaller than `n` in ascending order.

Constraints

  • 0 <= n <= 5 * 10^6

Examples

Input
n = 10
Output
[2, 3, 5, 7]
Why
Primes strictly less than 10 are 2, 3, 5, and 7.
Input
n = 2
Output
[]
Why
There are no prime numbers strictly less than 2.

Approach

  1. If n <= 2, return an empty list immediately since the smallest prime number is 2.

Solution

O(N log log N) time, O(N) space

Python
class Solution:
    def findPrimesLessThanN(self, n: int) -> list[int]:
        if n <= 2:
            return []
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        
        p = 2
        while p * p < n:
            if is_prime[p]:
                for multiple in range(p * p, n, p):
                    is_prime[multiple] = False
            p += 1
            
        return [i for i in range(2, n) if is_prime[i]]

Tips

  • What they are testing: Tests mathematical optimization and the Sieve of Eratosthenes algorithm over trial division.
  • Common mistake: Testing primality of each number individually up to sqrt(i), leading to O(N * sqrt(N)) which times out for large N.

Related SAP questions

Collected from public candidate posts and coding forums. Updated Nov 2026.