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?