Implement scalable prime generator

Q: Implement scalable prime generator

This question evaluates a candidate's ability to implement scalable prime generation and related algorithmic optimization, including algorithm selection, time and memory complexity reasoning, edge-case handling, and verification via unit tests.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Write a function first_n_primes(n) that returns the first n prime numbers in ascending order. Constraints:

1 ≤ n ≤ 100,000.
Aim for O(n log log n) expected time and near-linear memory.
Avoid repeated trial division per candidate; use an efficient sieve and a tight upper bound estimate for the nth prime.
Handle n=0 and n=1 edge cases cleanly.
Include unit tests for n ∈ {0,1,5,10,100,100000} and verify the last prime for n=100000 equals the known value.
Describe the complexity and key constants that dominate runtime for large n.

Implement scalable prime generator

Overview

Comments (0)