Proving the language of non-primes is in NP
If you created a deterministic polynomial-time algorithm $A$ that can check a &quot;yes&quot;-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$).