# BASH, 154 bytes

File `x.bash` (no trailing newline):

    a=2;while((l<$1));do if [ -n "${b[a]}" ]
    then((c=${b[a]}));else((c=a,l++));echo $a;fi;((d=a+c))
    while [ -n "${b[d]}" ];do((d+=c));done

Run:

    $ bash x.bash 5
    2
    3
    5
    7
    11
    $ bash x.bash 1000 | wc -l
    1000

----

Primes get calculated by letting known primes jump on the tape of positive integers. Basically it is a serialised Sieve Of Eratosthenes.

I don't have any idea about the O(n)... up to now....