A prime number
can be proved prime by exhibiting all the prime factors of
together with a witness
such that
but
for each prime divisor
of
. The primes
are then proved prime in the same way, except that 2 is assumed to be prime without proof. This recursive construction has a tree structure, which is shown here. These ideas prove that the prime numbers lie in the complexity class NP. If the input number is not prime, the next prime is used.
