Generate primes up to n efficiently
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that returns all prime numbers in the inclusive range 1..n. Requirements: handle n up to 10^7 efficiently (time and memory); return primes in ascending order. Follow-ups: 1) Provide a Sieve of Eratosthenes solution with time O(n log log n) and memory O(n). 2) For n up to 10^12 where memory is constrained, outline a segmented sieve and analyze complexity. 3) Discuss how you would adapt the sieve when the input is an arbitrary unsorted array of distinct integers from 1..n rather than the whole range.
Overview: This question evaluates algorithm design and complexity analysis for prime generation, focusing on sieving techniques and time-space trade-offs when producing primes up to large n.
Return all prime numbers in ascending order in the inclusive range 1..n using the Sieve of Eratosthenes.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: (10,)
Expected Output: [2, 3, 5, 7]
Explanation: Small primes.
Input: (1,)
Expected Output: []
Explanation: No primes.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.