How many random sieve operations to decimate the set {2,...,n}? 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$?
 A: An equivalent way of describing the process: We start with a randomly chosen permutation $\tau$ of $\{2, \dots, n\}$.  At each step we choose the first number in $\tau$ which is still in our set $S$, and apply the deletion process with that as our $k$.  A key property here:
An integer $x$ is chosen at some point if and only if x appears before all of its divisors in $\tau$
This is simply because if some divisor $y$ of $x$ appears before $x$, then either $y$ itself is chosen, or some divisor of $y$ (which is also a divisor of $x$) is chosen.  
In particular, the probability that $x$ is chosen at some point is $\frac{1}{d(x)-1}$, where $d(x)$ is the number of divisors of $x$.  This implies that the expected number of steps to decimation is 
$$\sum_{x=2}^n \frac{1}{d(x)-1}$$
I feel like this sum (or at the very least $\frac{1}{d(x)}$) has to be well-studied, but I don't have any references.  
A: I think the correct asymptotics should be rather $O(\frac{n}{\log n})$. That's because when you have $n$ numbers in your set and $n$ is large, then you knock out roughly $U^{-1}$ numbers, where $U$ is a Uniform$[0,1]$ random variable (indeed, if $k$ is chosen, then you through out approximately $\frac{n}{k}=\big(\frac{k}{n}\big)^{-1}$ numbers). Now, $\sum_{j=1}^m U_j^{-1}$ grows roughly as $m\log m$, so you need around $O(\frac{n}{\log n})$ steps to "considerably decrease" you set (say, to the size of $\frac{n}{\log n}$, since then it's enough to just decrease linearly).
Hopefully, this heuristics can be turned into proof, since on the "early stages" the "double-erasing attempts" (i.e., when you try to remove a number that was already removed before) shouldn't contribute a lot.
