another detail that the GP most likely left out on purpose is that the fact that easily checking divisibility means that primality is co-NP. Primality being NP

another detail that the GP most likely left out on purpose is that the fact that easily checking divisibility means that primality is co-NP. Primality being NP is actualy non-trivial (even before AKS). see wikipedia for more details: https://en.m.wikipedia.org/wiki/Primality_certificate https://en.m.wikipedia.org/wiki/Primality_certificate