Sieve Methods

Combinatorics · Axiom Academy

Applications of Inclusion-Exclusion in Combinatorial Counting A sieve is a process that filters out unwanted elements from a universal set. We start with all candidates and systematically remove those that don't meet our criteria. Think of it like a kitchen sieve: we pour a mixture through, and the unwanted parts are caught while the desired elements pass through. To find all prime numbers up to n , start with all integers from 2 to n . Then: Start with the smallest number (2) Cross out all its multiples (4, 6, 8, ...) Move to the next unmarked number and repeat Watch the animation below to see the sieve find all primes up to 30: 3. Connection to Inclusion-Exclusion The Sieve of Eratosthenes is actually an application of the inclusion-exclusion principle . Let's count how many primes exist up to n . Let A_p be the set of multiples of prime p in the range [2, n]. We want to count numbers that are in none of these sets: For any collection of properties P_1, P_2, ..., P_k, the number of elements satisfying none of these properties is:

This is the written version of the interactive lesson above. See the full Combinatorics course.