Is n a prime?

Randomly choose, say, 200 numbers between 1 and n. See if any of them divides n (in other words, if it is a witness to its compositeness). If none of the chosen numbers is a witness, then we declare that n is a prime. (There is a very very small possibility that this algorithm fails; this possibility is negligible because of the fact that for composite number n at least three-fourths of the numbers between 1 and n are witnesses to the compositeness of n.)

Algorithm by Michael O. Rabin