Za to se koriste drugi algoritmi. Pre svega, testovi pseudoprimalnosti, a ako bas hoces da budes siguran da je neki broj prost, onda su neki indijci pronasli algoritam polinomijalne slozenosti za testiranje primalnosti. No, i taj algoritam je isuvise skup za prakticnu primenu, pa se pribegava (aproksimativnim) testovima (pseudo)primalnosti.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.