Implement Function to Return First n Prime Numbers

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.

Return First N Prime Numbers

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)

Examples

Example 1

Input: n = 5
Output: [2,3,5,7,11]

Explanation: The first five primes are 2, 3, 5, 7, and 11.

Example 2

Input: n = 1
Output: [2]

Explanation: The first prime number is 2.

Hints

1. A sieve is efficient when you know an upper bound for the nth prime.
2. For n >= 6, p_n <= n(ln n + ln ln n) gives a usable upper bound.
3. Alternatively, generate primes incrementally by trial division using previously found primes up to sqrt(candidate).

Approach

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)