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)
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).