Count Primes Using Sieve of Eratosthenes

Problem Given an integer n, determine every prime number up to n and return how many primes are strictly below n.

Input / Output

• Input: a single integer n.
• Output: the count of primes strictly less than n (or, in the list variant, the primes themselves in ascending order).

Constraints

• 0 <= n <= 10^6-10^7. Per-number trial division costs O(n*sqrt(n)) and is too slow at the upper end.
• Memory must stay linear in n; a boolean or bit array of size n+1 is the expected working set.

Example

• n = 10 -> 4 (primes 2, 3, 5, 7).
• n = 2 -> 0 — the boundary case, since 2 is excluded when counting strictly below n.
• n = 0 and n = 1 -> 0.