I remember a long time ago when I drew a chart with all natural numbers up to some $n$ and then started crossing out composites to generate myself some primes. Something like this.
Today, I started sketching up some formulas.
I want to construct a formula to generate first $n$ primes from first $n$ natural numbers.
So far, I have a $10^\text{th}$ degree polynomial that works for $n\le10$ to generate first $10$ primes.
$$P(n)=( -2 n^{10} + 31 n^9 + 1260 n^8 - 46122 n^7 + 658854 n^6 - 5259177 n^5 + 25508240 n^4 - 75957388 n^3 + 133619808 n^2 - 124611264 n + 46327680) /120960$$
With my method so far, I can add the next prime on the list to the formula by expanding it for one extra degree. So with a $n^\text{th}$ degree polynomial formula, I would generate first $n$ primes using first $n$ natural numbers. Which is really bad or not so very good. I think.
How can I simplify this expression?
How complex would a first-$n$-primes formula be?
What are the best known methods of constructing such formulas?
What are the best such formulas so far?
In short, looking for some materials to study and/or your help to help me understand these things better.
I found this collection, but as far as I understand, "Prime-Generating Polynomials" are ranked on how much distinct primes they generate for some $n$s. I want to generate first $n$ primes as output using first $n$ natural numbers as input. (What's the best thing out there so far, and can I and how improve my expression so far?)
Update
I've done a quick search on "Lagrange interpolation" as Friedrich Philipp suggested and among other things, stumbled upon this answer of a similar question.
But I'm not strictly limited to polynomials. I just want them to come up in order from first to $n^\text{th}$ prime. Are there any better alternatives or is this the best thing I'll get so far?
If you really want a formula, there are very complex and not very useful in terms of speed and cost of calculation, but beautiful from the perspective of the theory, constructions. In this previous question, there is an example of a formula of the prime counting function based on Wilson's theorem, and the formula is true only if (credits to Dylan in the explanation of the previous question):
$\displaystyle f(j)=\frac{\sin^2\left(\pi\frac{(j-1)!^2}{j}\right)}{\sin^2\left(\frac{\pi}{j}\right)}$ has value $1$ when $j$ is prime and $0$ in the rest of cases.
Thus you could construct a formula for primes like this:
So if you run a loop it should provide the list of primes and $0$'s as follows:
$[1,2,3,4,5,6,7,8,9,10,11...] \to [0,2,3,0,5,0,7,0,0,0,11...]$
In this way, it would not be required to build a complex polynomial to obtain the list.