Print all prime numbers smaller than N
Filed under SAP
Free read 1 of 3If 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
If n <= 2, return an empty list immediately since the smallest prime number is 2.
Use a boolean array `is_prime` of size `n` initialized to True, setting indices 0 and 1 to False.
For each `p` from 2 up to `sqrt(n)`, if `p` is prime, mark its multiples starting at `p*p` as composite.
Iterate through the array and gather all indices that remain marked True.
Solution
O(N log log N) time, O(N) space
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.