Ehhez használható a Fermat-(vagy az Euler-?)tétel. Valami iteráció, ami mindig kizárja a lehetséges osztóknak (vagy azoknak a számoknak, amelyek x-szel nem relatív prímek?) legalább a felét, így viszonylag kevés lépés után (n) nagy valószínűséggel (1>p>1-2^(-n)) mondhatod egy számról, hogy prím. Még rémlik, hogy vannak a csúnya Carmichael (?) számok, amelyek összetettségük ellenére prímnek mutatják magukat minden esetben a próba során, és hogy ezeket is ki lehet cselezni valahogy. Sajnos a részletek a feledés homályába merültek... Így visszaolvasva túl sok a kérdőjel. :(