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.