Exercise 1004Combinatorics › Inclusion-exclusionL1Added 3 Nov 2026

The sieve of Eratosthenes as IE

#IE#sieve#primes

Statement

Use IE to count primes up to $30$ .

Hint

Apply the sieve: exclude multiples of $2,3,5$ (primes up to $\sqrt{30}$ ), then handle the primes $2,3,5$ separately.

Show solutionHide solution

Multiples of $2,3,5$ up to $30$ . From IE: $15+10+6-5-3-2+1=22$ .

Not divisible. $30-22=8$ integers not divisible by $2,3,5$ up to $30$ : $1,7,11,13,17,19,23,29$ .

Primes. Excluding $1$ , and adding $2,3,5$ : $7+3=10$ primes.

Conclusion. $\pi(30)=10$ .