How does the Sieve of Eratosthenes work?

Question presented to candidate: "Explain how the Sieve of Eratosthenes finds all primes up to n, then implement it in Python. Why does the inner loop start at p squared, and what is the time complexity?"

What a strong answer should cover:

• The idea: mark every number as candidate prime, and for each prime p cross out its multiples; survivors are prime.
• The two optimisations: start at p² (smaller multiples were crossed by smaller primes) and stop once p² > n.
• O(n log log n) time vs O(n√n) for trial division on every number; O(n) space.
• Variations: smallest-prime-factor sieve for factorisation, segmented sieve for a window [L, R].
• Python details: use a bytearray (1 byte per flag) rather than a list of bools (an 8-byte reference per flag), and slice assignment flags[p*p::p] = bytes(k) so the crossing loop runs in C; math.isqrt for an exact square root.

Clarifying questions expected:

• Is n inclusive, and how large can it be?
• Do you need the list, the count, or fast lookups?

Code / implementation expected: Yes — a sieve in Python 3 returning the primes (or the count) up to n.