# BASH, 133 bytes

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

    a=2
    while((l<$1));do if((b[a]))
    then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
    while((b[d]));do((d+=c));done
    ((b[d]=c,a++));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.

    from time import time as t
    
    L = {}
    n = 2
    l = 0
    
    t0=t()
    
    while l<1000000:
    
            if n in L:
                    P = L[n]
            else:
                    P = n
                    l += 1
                    print t()-t0
    
            m = n+P
            while m in L:
                    m += P
            L[m] = P
    
            n += 1

...is the same alrorithm in Python and prints out the time when the `l`-th prime was found instead of the prime itself.

This output plottet with `gnuplot` by...

    plot "fsoe3-timing.dat"

...yields the following:

[![enter image description here][1]][1]

The gaps probably have something to do with file i/o delays due to writing buffered data to disk...

...so getting an idea of the complexity by looking at the experimental data does not really help a lot... :-(

  [1]: https://i.sstatic.net/hTKLH.png