Runtime analysis of prime-set computation
The key is already shown in your link: each composite number is marked only once in this algorithm.

Consider a composite number $x=p_1^{\alpha_1} p_2^{\alpha_2}\cdots$ where $p_1&lt;p_2&lt;\cdots$ are primes and $\alpha_1,\alpha_2,\ldots$ are positive integers. In the iteration for $p_i$ ($i&gt;1$), note $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ has been deleted from $L$ in the iteration for $p_1$ because $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ is a multiple of $p_1$, so $x$ will not be marked in the iteration for $p_i$. As a result, $x$ will be marked only once in the iteration for $p_1$.

In each iteration, traveling the list costs the same asymptotically as the marking process, because each element in the list corresponds to a number to be marked. 

Hence the total time is equal to the time for marking asymptotically, which is $O(n)$.