Generate primes up to n efficiently

Given a single integer n, return every prime number that lies in the closed interval [1, n]. The result must be sorted in increasing order. Your solution should be efficient enough to handle values of n up to $$5 \times 10^6$$ within reasonable time and memory limits. After completing the base implementation, answer the following follow-up questions: Provide a Sieve of Eratosthenes implementation that runs in $$O(n \log \log n)$$ time and uses $$O(n)$$ memory. For inputs as…