I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is :
we are maintaing a one pointer from node $i$ of the list $L$ to index $i$ of array $N$ and one pointer from index $i$ of $N$ to $i$th node of list $L$. We will use a doubly linked list in such a way that we mark each element of $N$ exacly once.
- Pick the smallest unmarked element $i \ge 2$ in $N$ and add $i$ to $Q_{k-1}$.
- Starting from the first node, walk up the list $L$ in increasing order until we find the smallest number $r$ in it such that $r\cdot i \ge k-1$.
- Walk down the list $L$ (crucially, in decreasing order) from the node $r$, and for each $l$ in $L$, seen, mark the element $N[i\cdot l]$ and delete the node containing $i\cdot l$ from $L$ ( this node in $L$ is accessed through the pointer from the $(i\cdot l)$th location in $N$ ).
- If $N$ has any unmarked element $\ge 2$, go back to first step
In the first round all the multiple of 2 will get marked. It is easy to verify that each element in the array will get marked just once.
Question : How to show that above algorithm has Running time $O(k)$?
After first iteration all multiples of 2 will be marked in the array $N$ and all multiples of 2 will be removed from the list $L$. In the second iteration multiples of 3 and so on.
$$ \begin{align*} \text{Total time}: &= c_1k + c_2\frac{k}{2} +c_3\frac{k}{2 \times 3} +c_4\frac{k}{2 \times 3 \times 5} + c_5 \frac{k}{2 \times 3 \times 5 \times 7}+\cdots\\ &=k \left(c_1 + c_2\frac{1}{2} +c_3\frac{1}{2 \times 3} +c_4\frac{1}{2 \times 3 \times 5} + c_5 \frac{1}{2 \times 3 \times 5 \times 7}+\cdots \right) \\ &= O(k) \end{align*} $$
Reference : link