How to compute all primes between upto $n$ in time $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.