COMPOSITE $\in$P if and only if PRIME $\in$ P 
Let COMPOSITE be the following decision problem.
   COMPOSITE
   Input:
  an integer $n \geq 2$.
  Question: is n composite?
   Show that
  COMPOSITE $\in$P if and only if PRIME $\in$ P.

I think I must take an algorithm for COMPOSITE. This gives an algorithm for PRIME
by simply negating its answer. 
 A: The short answer is yes, your thinking is correct. If we had, say, a poly-time deterministic algorithm to decide PRIME, then we could make a poly-time algorithm for COMPOSITE by running the primality algorithm on the input and negating the answer. Simple enough, but we can do even better if we're careful about the details.
For PRIME, one way to go about this would be to test trial divisors up to $\sqrt n$: if a trial divisor $d$ divided our candidate, $n$ the algorithm would halt and answer "false". If it got to the end without finding any divisors, it would halt and answer "true".
However, for a decision problem $X$ to be in P, there must be an algorithm that decides $X$ in time polynomial in the length of the input (in bits, say). Testing trial divisors would take at least $\sqrt{n}$ time, even if we could divide in constant time (which we obviously can't). When testing a number $n$ we have that the length, $d$, of the input is about $\log n$, so trial division will take at least $2^{d/2}$ time, which is exponential in the length of the input.
All is not lost, though. In 2002, Agrawal, Kayal, and Saxena developed a prime testing algorithm that runs in time polynomial in the length of its input. Using the logical negation of this algorithm's output would not only answer your original question, but it would actually produce an algorithm for COMPOSITE that was in P.  
A: One of the easiest, though perhaps not of the thriftiest, algorithms to find out whether a number is a prime or not is:
Divide a natural number $\,n\,$ by $\,i=1,2,...,\lfloor \sqrt n\rfloor\,$ . If none of the divisions is a natural number (say, if all the residues are greater than zero) $\,n\,$ is prime.
