Let $S$ be the set of integers $\{2,3,4,\ldots,n\}$. Consider the following process:

- Select a random element $k \in S$.
- Remove from $S$ every number divisible by $k$.
- Repeat with this reduced $S$.

I am interested in the number of repetitions $\sigma(n)$ needed to reduce $S$ to the empty set.

Example, $n=10$: \begin{eqnarray} \# &:& 2,3,4,5,6,7,8,9,10\\ 10 &:& 2,3,4,5,6,7,8,9\\ 9 &:& 2,3,4,5,6,7,8\\ 3 &:& 2,4,5,7,8\\ 4 &:& 2,5,7\\ 5 &:& 2,7\\ 7 &:& 2\\ 2 &:& \varnothing \end{eqnarray} Limited data suggests that the number of sieve operations $\sigma(n)$ needed to decimate the set $S$ might grow approximately linearly with $n$:

^{ Number of random sieve iterations to decimate the set $\{2,3,\ldots,n\}$. }

^{ Each point plotted is the average of $10$ simulations. }

The slope is about $0.28$ (without any careful statistics).

Perhaps it is possible to estimate $\sigma(n)$ for large $n$?