## Sieve of Eratosthenes

How many numbers will remain from the sequence $$1,…,n$$ after we cross out all multiples of 2, 3, 5 and 7?

First solve the problem in general and then determine a precise result for $$n=999$$.

• #### Solution

For $$i\in\{2{,}3,5{,}7\}$$ let $$A_i$$ be set of multiples of $$i$$ in the set $$\{1,…,n\}$$ and similarly $$A_I=\bigcap\limits_{i\in I} A_i$$ for $$I\subseteq\{1,…,n\}$$. So $$A_2$$ are the odd numbers, $$A_{\{2{,}5,7\}}$$ are the multiples of 70 and so on.

We have $$|A_I|=\left\lfloor\frac{n}{\prod I}\right\rfloor$$. By the inclusion-exclusion principle, after crossing the numbers out we are left with $$n-\left|\bigcup\limits_{i\in\{2{,}3,5{,}7\}} A_i\right|= n+\sum\limits_{I\subseteq\{2{,}3,5{,}7\},I\ne\emptyset}(-1)^{|I|} |A_I|= n+\sum\limits_{I\subseteq\{2{,}3,5{,}7\},I\ne\emptyset}(-1)^{|I|} \left\lfloor\frac{n}{\prod I}\right\rfloor$$.

In paticular for $$n=999$$ we have $$A_2=499$$, $$A_3=333$$, $$A_5=199$$, $$A_7=142$$, $$A_{\{2{,}3\}}=166$$, $$A_{\{2{,}5\}}=99$$, $$A_{\{2{,}7\}}=71$$, $$A_{\{3{,}5\}}=66$$, $$A_{\{3{,}7\}}=47$$, $$A_{\{5{,}7\}}=28$$, $$A_{\{2{,}3,5\}}=33$$, $$A_{\{2{,}3,7\}}=23$$, $$A_{\{2{,}5,7\}}=14$$, $$A_{\{3{,}5,7\}}=9$$ and $$A_{\{2{,}3,5{,}7\}}=4$$.

Now it remains to compute $$999-499-333-199-142+166+99+71+66+47+28-33-23-14-9+4=228$$.  