To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.
A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).
So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).
To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).
And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.
See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/
