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$.

• For $j=2$ to $j=\sqrt n$

• 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?

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.

StackExchange Computer Science Q#87602, answer score: 5