Generate primes up to n efficiently

Q: Generate primes up to n efficiently

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.

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

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.

Generate primes up to n efficiently

Overview

Comments (0)