Generate primes up to n efficiently

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.