Sieve of Eratosthenes

Task number: 3486

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

  • Answer

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

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email