Count Primes Using Sieve of Eratosthenes

Problem: Given a number n, efficiently determine which numbers up to n are prime (or count primes below n).

Constraints: n can be as large as 10^6-10^7, ruling out per-number trial division.

Example: Input: n=10 Output primes: [2,3,5,7]

Approach: Use the Sieve of Eratosthenes: create a boolean array of size n+1 initialized to true, mark 0 and 1 as non-prime, then for each number p starting at 2, if still marked prime, mark all multiples of p (starting from p*p) as non-prime. This runs in O(n log log n) time and O(n) space.