prime_fermat, a C++ code which applies Fermat's primality test to an integer n, which always correctly identifies primes, but sometimes also accepts nonprimes. Nonetheless, the test is useful for weeding out most nonprimes. The accuracy of the test can be improved by running it for several bases.
The test is based on Fermat's little theorem. If n is prime, and a is any number not divisible by n, then
a^(n-1) = 1 mod n.
To test whether n is prime, we can pick a random value a and see
if the congruence holds. If it does not, then n is definitely not
prime. If it holds, we are not sure. We can repeat the test for
several values of a to improve our confidence.
The information on this web page is distributed under the MIT license.
prime_fermat is available in a C++ version.
is_prime, a C++ code which determines if a given integer n is prime, using various versions of the sieve of Eratosthenes.
prime, a C++ code which counts primes between 1 and N, intended as a starting point for the creation of a parallel version.
prime_mpi, a C++ code which counts the number of primes between 1 and N, using MPI for parallel execution.
prime_openmp, a C++ code which counts the number of primes between 1 and N, using OpenMP for parallel execution.
prime_pi, a C++ code which evaluates Pi(n), the number of primes less than or equal to an integer n.