Formalizing the "no formula for primes" intuition
[Certainly not a complete answer, but too long for a comment]

Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but here it's about whether there's a formula that's sufficiently simple that you could use it to help decide whether a given DFA accepts any primes.)

In another direction, given that your conjecture is about the difference between cubic and quadratic, it might be reasonable to think about whether the problem is complete for cubic time under sub-cubic reductions (see Vassilevska Williams &amp; Williams). It looks tricky, or even unlikely, since it's so different from the other "cubic-complete" problems, like all-pairs shortest paths, triangle detection, etc., but could be worth considering nonetheless. Their framework was in the context of deterministic algorithms, but it shouldn't be too hard to adapt to randomized...