Prime number

In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. Or for short: A prime number is a natural number with exactly two natural divisors. A natural number that is greater than one and is not a prime is called a composite number. The numbers zero and one are neither prime nor composite. The property of being a prime is called primality. Prime numbers are of fundamental importance in number theory.

Primality tests

Main article primality test

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A primality test algorithm is an algorithm which tests a number for primality, i.e. whether the number is a prime number.

Related Topics:
Primality test algorithm - Algorithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• AKS primality test
• Fermat primality test
• Lucas-Lehmer test
• Lucas-Lehmer primality test
• Solovay-Strassen primality test
• Miller-Rabin primality test

A probable prime is an integer which, by virtue of having passed a certain test, is considered to be probably prime. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes.

Related Topics:
Probable prime - Carmichael number - Pseudoprime

~ ~ ~ ~ ~ ~ ~ ~ ~ ~