I am trying to understand something, this is what I was thinking. (Do not dare laugh!)

A number is prime if and only if,
\left[ \frac{(n-1)!+1}{n} \right]=\frac{(n-1)!+1}{n}.
If an algorithm is made to run based on this rule, what would be its complexity? I am thinking that since Striling's Forumla shows the factorial behaves like an exponential then its complexity is exponential, right?

Now, since its runs in non-deterministic polynomial time there cannot exits a algorithm having complexity in polynomial time. (Because P verses NP). This explains the difficulty of having efficient primality testing.