Implement Function to Return First n Prime Numbers
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Quick algorithm screen to gauge Python fluency.
##### Question
Implement a Python function that returns the first n prime numbers.
##### Hints
An optimized sieve or trial-division with memoization keeps it simple and efficient.
Quick Answer: This question evaluates algorithmic problem-solving and basic number-theory competency by requiring generation of prime numbers with attention to correctness and performance characteristics.
Given an integer n (0 <= n <= 100000), return the first n prime numbers in ascending order. If n is 0, return an empty list.
Constraints
- 0 <= n <= 100000
- Return primes in ascending order
- If n = 0, return []
- Use an efficient approach (e.g., sieve or optimized trial division)
Solution
from math import log
def first_n_primes(n: int) -> list[int]:
"""
Return the first n prime numbers in ascending order.
Uses a sieve sized via an upper bound for the nth prime and grows if needed.
"""
if n <= 0:
return []
if n == 1:
return [2]
# Upper bound for nth prime (Rosser's theorem) for n >= 6:
# p_n <= n (ln n + ln ln n). Use a small safety offset.
if n < 6:
limit = 15
else:
nn = float(n)
limit = int(nn * (log(nn) + log(log(nn))) + 3)
while True:
sieve = bytearray(b"\x01") * (limit + 1)
if limit >= 0:
sieve[0] = 0
if limit >= 1:
sieve[1] = 0
m = int(limit ** 0.5)
for p in range(2, m + 1):
if sieve[p]:
start = p * p
sieve[start:limit + 1:p] = b"\x00" * ((limit - start) // p + 1)
primes = [i for i, is_prime in enumerate(sieve) if is_prime]
if len(primes) >= n:
return primes[:n]
# If the bound was too small, grow and retry
limit = int(limit * 1.5) + 1
Explanation
We generate primes using a sieve with a size chosen from a known upper bound for the nth prime: for n >= 6, p_n <= n(ln n + ln ln n). We handle small n explicitly. After sieving up to the bound, if the number of primes is still less than n, we grow the bound and repeat. Using a bytearray for the sieve is memory efficient, and slicing assignment quickly marks composites.
Time complexity: O(L log log L), where L is the final sieve limit ≈ n (ln n + ln ln n) for n >= 6. Space complexity: O(L).
Hints
- A sieve is efficient when you know an upper bound for the nth prime.
- For n >= 6, p_n <= n(ln n + ln ln n) gives a usable upper bound.
- Alternatively, generate primes incrementally by trial division using previously found primes up to sqrt(candidate).