Quick Overview

This question evaluates algorithmic problem-solving and basic number-theory competency by requiring generation of prime numbers with attention to correctness and performance characteristics.

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.

Overview: 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

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

Loading coding console...

Show the approach

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)