I am trying to understand something, this is what I was thinking. (Do not dare laugh!)
A number is prime if and only if,
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.