Sieve formula

#sieve#inclusion-exclusion#primes

Statement

Use inclusion-exclusion to count numbers up to $100$ not divisible by $2$ , $3$ , or $5$ .

Hint

Complement of the union.

Show solutionHide solution

From earlier. $|A_2\cup A_3\cup A_5|=74$ .

Complement. $100-74=26$ .

Conclusion. $26$ numbers coprime to $30$ up to $100$ .

Remark. This is the sieve of Eratosthenes for primes $\ge7$ .