Można pokazać, że PRIMES należy do klasy coNP: jego dopełnienie COMPOSITES należy do NP, gdyż można łatwo niedeterministycznie stwierdzić, że jakaś liczba jest złożona – zgadując jej dzielniki.

W 1975 roku, Vaughan Ronald Pratt pokazał, że istnieją certyfikaty pierwszości: sprawdzalne w czasie wielomianowym dowody, że dana liczba jest pierwsza. Tym samym udowodnił, że język PRIMES należy też do klasy NP, a więc należy do przecięcia NP ∩ coNP.

Kolejne algorytmy Solovay-Strassena i Millera-Rabina umieściły język PRIMES w klasie coRP (jego dopełnienie należy do RP, czyli klasy problemów, dla których istnieje probabilistyczna maszyna Turinga działająca w czasie wielomianowym, która zwraca „nie” zawsze, kiedy prawidłową odpowiedzią jest „nie”, i zwraca „tak” (z prawdopodobieństwem, które dla żadnych danych nie spada poniżej pewnej wartości) lub „nie”, kiedy prawidłową odpowiedzią jest „tak”). W 1992 roku algorytm Adlemana-Huanga zmniejszył złożoność problemu do ZPP = RP ∩ coRP, poprawiając wynik Pratta.