An algorithm for getting $n$ primes
Given $n$, let $M = 2n\log n$ (here $2$ is any constant larger than $1$). Put all numbers from $2$ to $M$ in a linked list. Now implement Eratosthenes sieve, by repeatedly running the following algorithm, until you get $n$ primes. Look for the first unmarked number $p$ (they all start unmarked; start looking at the previous prime), take it as a prime, and mark every integer in hops of length $p$. The running time is roughly $M + \sum_p M/p = \Theta(M\log\log M) = \Theta(n \log n \log\log n)$, where $p$ goes over the first $n$ primes. Since the $k$th prime $p_k$ is about $k\log k$, heuristically indeed
$$ \sum_{k=1}^n \frac{1}{p_k} \approx \sum_{k=2}^n \frac{1}{k\log k} \approx \int_2^n \frac{dk}{k\log k} \approx \log\log n.$$
This approximation can be proved rigorously, this is one of the results known as Mertens' theorem.

See Emil's comment below or the Wikipedia article for improvements on this algorithm.

Edit: Before Emil's comment, I suggested implementing the algorithm using a linked list, but that's a bad suggestion since you can't "hop" in a linked list, causing the runtime to be $\Omega(n^2)$.