# Formalizing the "no formula for primes" intuition

I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:

Conjecture: There is no $$O(n^2)$$ expected time randomized algorithm to generate $$\ge n$$-bit primes.

Currently I believe the best algorithm has conjectured complexity $$\tilde{O}(n^3)$$: run the $$\tilde{O}(n^2)$$ Lucas-Lehmer test on $$O(n)$$ Mersenne numbers. We could go from $$n^3$$ to $$n^2$$ using the same sample-and-check strategy if a faster $$\tilde{O}(n)$$ checking algorithm is found. (This argument for the choice of 2 as exponent due to Paul Christiano.)

However, if a "formula for primes" existed, and was sufficiently simple, the fact that arithmetic is quasilinear means that we might get a quasilinear time prime generation algorithm, or $$\tilde{O}(n)$$. Conjecturing that the minimum exponent is 2 roughly approximates "the best strategy is sample-and-check".

Two questions:

1. Is there any heuristic evidence beyond the algorithms discovered so far about the optimum primality testing exponent, or the optimal exponent for generating primes?
2. Are there other attempts at formalizing the "no formula for primes" intuition?

I should clarify that of course I know that settling the conjecture is hopeless: I’m looking for heuristics only.