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.

Finding prime numbers

The Sieve of Eratosthenes is a simple way and the Sieve of Atkin a fast way to compute the list of all prime numbers up to a given limit.

Related Topics:
Sieve of Eratosthenes - Sieve of Atkin

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In practice though, one usually wants to check if a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime N. After several iterations, they declare N to be "definitely composite" or "probably prime". These tests are not perfect. For a given test, there may be some composite numbers that will be declared "probably prime" no matter what witness is chosen. Such numbers are called pseudoprimes for that test.

Related Topics:
Probability - Primality test - Pseudoprime

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A new deterministic algorithm which finds whether a given number N is prime where the time required is a polynomial function of the number of digits of N (i.e. of the logarithm of N) has recently been described.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~