Is there a sequence producing almost all primes? Is there a sequence which contains only primes and $$\lim_{n \to \infty} \frac{a_n}{p_n} = 1$$ (where $p_n$ is the $n$th prime)?
Edit: sigh. I meant a sequence produced using 0, 1, +, -, *, / used a constant amount of times, powers to a constant and any constant number of the previous elements.
 A: Apart from the trivial solution mentioned in the comments, if you exclude a finite number $k$ of primes, then $a_n=p_{n+k}$ for $n\geq N$ for some $N$ and even in this case you have
$$ \lim_{n\to \infty} p_{n+k}/p_n=1$$
(See Cipolla's asymptotic expansion).
If you exclude primes in arithmetic progression, i.e. $a_n=p_{rn}$ for some $n$, then the limit is $r$.
On the other hand I would be surprised if the sequence $a_n$ of all primes but skipping Mersenne's primes doesn't verify what you want. Or all primes skipping twin primes. Or all primes skipping any set of rare primes.
Or if $a_n$ allow repetitions, you can find a lot more examples. For instance any set of primes in where you replace a subset of zero density of primes by the prime "2".
With the additional constraints on $a_n$ you gave, in any case solution $a_n$ to your problem has to match Cipolla's asymptotics, which are precise. I don't see how to do that with the given operations (they generate rational and exponential functions).
A: Primes become less common as integers become larger. This includes primes of certain forms, polynomial values and sequences. The Mersenne Numbers $2^n-1$ with $n$ prime have the condition that each divisor of $2^n-1$ must be of the form $8kn+1$ or $8kn-1$, raising the probability of them being prime compared to a random integer $N$ of similar size, however, primes of the form $2^n-1$ are still extremely rare. 
