gen-briefly-explain-the-sieve-of-eratosthenes-and-one-common-mis-922c

Briefly explain the sieve of Eratosthenes and one common misconception about it.

# Sieve of Eratosthenes **How it works:** The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. You: 1. List all numbers from 2 to your limit 2. Start with 2 (the first prime), mark it as prime, then cross out all its multiples 3. Move to the next unmarked number, mark it as prime, and cross out all its multiples 4. Repeat until you've processed all numbers 5. All unmarked numbers are prime **Common misconception:** Many people think the sieve "tests" each number for primality by checking divisibility. In reality, it works by *elimination* — it directly marks composites (non-primes) by identifying them as multiples of smaller primes. No division is performed; it's purely an iterative marking process, which is why it's so efficient.