Is there a one-to-one function from the natural numbers to the primes? Is there a function $f : \mathbb N \rightarrow \mathbb P$, where $\mathbb P = \{p \in \mathbb N \mid \ p$ is prime$\}$, such that $f$ is injective?
It is known that no such polynomial function exists.
Also, I wish to exclude functions defined as $f(n) = \text{the $n$th prime}$, which requires one to find primes in advance.
 A: Here is something that I have established a long time ago.
The answer to your question is $P_n$, but please note that it is "computationally worthless".

Is $n$ prime:
$$F_n=\left\lfloor\frac{\left(\sum\limits_{k=2}^{n-1}\left\lceil\frac{{n}\bmod{k}}{n}\right\rceil\right)+2\cdot\left\lceil\frac{n-1}{n}\right\rceil}{n}\right\rfloor$$

How many primes until $n$:
$$G_n=\sum\limits_{k=2}^{n}F_k$$

What is the $n$th prime number:
$$P_n=\sum\limits_{k=n}^{n^2+1}{k}\cdot{F_k}\cdot\left(1-\left\lceil\frac{(G_k-n)^2}{(G_k+n)^2}\right\rceil\right)$$
A: Have you heard of Mills' constant? The function defined below, with $A$ being Mills' constant, always gives a prime:
$$f(n)=\left\lfloor A^{3^n}\right\rfloor$$
A: We cannot completely rule out the possibility that a "simple" and "natural" function exists which very quickly enumerates a (possibly very thin) infinite subset of the primes.
For example it is not known if Catalan–Mersenne numbers are all primes, 2, 3, 7, 127, 170141183460469231731687303715884105727, ... (OEIS A007013). It would be a tremendous surprise if they were.
The practise of competing to find the largest known prime, and prizes like the EFF Cooperative Computing Awards, would become meaningless if someone could prove that all Catalan–Mersenne numbers are prime.
I have not heard of any mathematician believing that huge primes can be found that easily.
A: Coming from theoretical computer science, I'd formalize your question as 

Is there a bijection $f: \mathbb{N} \to P$ so that $f(n)$ can be computed in time polynomial in $\lceil \log_2 n\rceil$ (the number of bits of $n$)?

This is a standard way to formulate such "explicit indexing" questions. The requirement that $f$ be efficiently computable is a strong version of requiring that $f$ is "explicit". It also excludes things like computing all the primes up to $n$. 
The question stated above is certainly open! The closest result I know to it is a recent paper that shows how to explicitly index irreducible polynomials of a given degree in a finite field. Such polynomials are the "primes" in the ring of polynomials but have much more structure than the primes in the ring of integers.
A: The restatement by Sasho Nikolov seems to make more sense. Though you can probably drop the bijection requirement. 
Otherwise the answer to the original question as stated is yes. There are at $\mathfrak{c}$-many injective functions from $\mathbb{N}$ to $\mathbb{P}$ since both of the sets in question have size $\aleph_0$.
There are even computable such functions (since deciding whether a number is prime is not only computable but actually in P).
While writing this I wonder whether a little bit of work using some knowledge about prime density and the poly time deterministic primality prover you couldn't get an almost P algorithm just by finding the closest prime to a suitably chosen power of $n$.
The following springs to mind; compute $n^{2}$, use poly time primality prover to check $n^2+i$ for primality for $i>1$. For each $i$ this is then polynomial in $\log_2(n)$ and given that $$\lim_{x\rightarrow\infty}\frac{\pi(x)}{x/\ln(x)}=1$$ assymptotically the number of $i$'s tested will also be polynomial .
As far as I can tell this give an injective polynomial time function from $\mathbb{N}$ to $\mathbb{P}$. If anyone sees a problem please comment.
