It is easy to show that PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can decide compositeness by nondeterministically guessing a factor. PRIMES est dans co-NP ː en effet, son complémentaire COMPOSITES est dans NP car on peut décider COMPOSITES en temps polynômial sur une machine non déterministe en devinant un facteur.
