Primality test

For example, consider the number 100, which is evenly divisible by these numbers:

All even numbers greater than 2 can also be eliminated: if an even number can divide n, so can 2.

Although this method requires about p modular multiplications, rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.

The following is a primality test in the C family of languages using the same optimization as above.

The following is a primality test in V using the same optimization as above.

The following is a primality test in JavaScript using the same optimization as above.

The following is a primality test in R (programming language) using the same optimization as above.

The following is a primality test in Dart (programming_language) using the same optimization as above.

The following is a primality test in Freepascal using the same optimization as above.

The simplest probabilistic primality test is the Fermat primality test (actually a compositeness test). It works as follows:

The Miller–Rabin and the Solovay–Strassen primality tests are simple and are much faster than other general primality tests. One method of improving efficiency further in some cases is the Frobenius pseudoprimality test; a round of this test takes about three times as long as a round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin.