Collection of Maths Problems

Sieve of Eratosthenes

Task number: 3486

• 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\).

• Answer

  Only 228 numbers will remain after we cross the others out.