# Proving the language of non-primes is in NP

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.

Show the following language is in NP:

Not-Prime = {n ∈ N: n is not a prime number}

So far, I have created an efficient decider for the language with a certificate, but I'm not sure how to prove that the language is actually in NP. Thank you for any advice!

If you created a deterministic polynomial-time algorithm $$A$$ that can check a "yes"-certificate for Not-Prime (of polynomial length in the size of instance), then you already proved that your problem is in $$\mathsf{NP}$$.
Say that a polynomial upper bound on the length of the certificate is $$p(s)$$, where $$s$$ is the size of the instance. A non-deterministic polynomial-time algorithm for Not-Prime can do the following:
• Guess the length $$\ell$$ of the certificate in $$\{0, \dots, p(s)\}$$.
• For $$i=1, \dots, \ell$$: guess the $$i$$-th bit $$c_i$$ of the certificate.
• Run $$A$$ on the certificate $$c_1 c_2 \dots c_\ell$$. If $$A$$ accepts, accept. Otherwise reject.
A certificate for an instance $$n$$ of Not-Prime is just a non-trivial prime factor of $$n$$ (which requires at most $$\lceil \log n \rceil$$ bits to be represented, so you can pick $$p(s)=s$$).