Implement Sieve of Eratosthenes to find all primes up to 10^7. Then extend to: (1) Segmented sieve for range [L,R] where R-L ≤ 10^6, R ≤ 10^12, (2) Smallest Prime Factor (SPF) sieve for O(log n) factorization, (3) Count primes in range using prefix sums. Analyze time and space complexity of each variant.
