# How to compute all primes between upto $n$ in time $O(n)$ time?

Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$.

1. For $j=2$ to $j=\sqrt n$
2. mark multiples of $j$ from $A$

Running time of this algorithm is $O(n \log n).$ It is easy to see that after first iteration there will be $n/2$ many unmarked elements and so on.

The problem with this method is that some of the elements may be marked more than one time.

Question : How to compute all the primes upto $n$ in $O(n)$ time?

• If you only go over primes (which you can do at no cost), you improve the running time to $O(n\log\log n)$. – Yuval Filmus Feb 1 '18 at 12:56
• Does it help if you put all elements in a (doubly)linked-list and then do the marking-trick, but instead of marking an element; you simply remove it from the list (removing can be done in $O(1)$)? This solves the "marking things twice" issue. [I am not saying that in practice; this is a good idea] – user53923 Feb 1 '18 at 13:10
• Why would you try to mark multiples of 4? – gnasher729 Feb 1 '18 at 16:21
• Your algorithm is a degenerated version of Eratosthenes sieve, where for each j, if j has not been marked before, you mark all its multiple. The running time is thus rougly \sum_{p prime <= n} n/p which is O(n log (log n)) (en.wikipedia.org/wiki/…): not enough but not that bad already. – holf Feb 1 '18 at 17:42
• @gnasher729 I now notice that did not read the algorithm in the question correctly - I meant to say that you only use the elements that remain in the linked-list for the marking (smallest to largest) (since 4 is removed after doing the marking with 2; it will not be considered) – user53923 Feb 2 '18 at 9:26

You can use a sieve to enumerate all prime numbers up to $n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in $O(n)$ time.