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 :

enter image description here

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.

  1. Pick the smallest unmarked element $i \ge 2$ in $N$ and add $i$ to $Q_{k-1}$.
  2. 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$.
  3. 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$ ).
  4. 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

  • $\begingroup$ This is the Eratosthenes sieve, whose running time is $O(n\log\log n)$. $\endgroup$ Feb 11, 2018 at 18:55
  • $\begingroup$ The answer to a prior question of yours already described how to compute this set in $O(k)$ running time, and gave you references that analyze the running time of various algorithms of this sort (including the algorithm you describe, I believe): cs.stackexchange.com/q/87602/755 $\endgroup$
    – D.W.
    Feb 12, 2018 at 0:27
  • $\begingroup$ @Yuval Filmus No the running this is a special case of " sieve of Atkin " whose run-time is $O(k)$. you can check the link given above and in the reference part (second reference 2 ,page 990, second last paragraph) $\endgroup$
    – Complexity
    Feb 12, 2018 at 5:44
  • $\begingroup$ @D.W. Algorithm is clear to me to some extent. This question if for runtime analysis. $\endgroup$
    – Complexity
    Feb 12, 2018 at 5:47
  • $\begingroup$ How do you get the total time formula? Could you please explain more? $\endgroup$
    – xskxzr
    Feb 12, 2018 at 9:55

2 Answers 2


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<p_2<\cdots$ are primes and $\alpha_1,\alpha_2,\ldots$ are positive integers. In the iteration for $p_i$ ($i>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)$.


Now while this has a nice big-O value, you use one pointer in the array, and one node containing two pointers for every integer in this range.

Using for example 1GB of memory, you can construct a sieve with 1 bit for each odd integer, or 16 billion integers. Using 3 pointers per integer, using 4 byte per pointer lets you handle just 83 million integers, almost 200 times fewer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.