## Prime number - Wikipedia, the free encyclopedia

--------------------

** Prime number **

"Prime" redirects here. For other uses, see Prime (disambiguation).

A *prime number* (or a *prime*) is a natural number greater than 1 that has
no positive divisors other than 1 and itself. A natural number greater than
1 that is not a prime number is called a composite number. For example, 5
is prime because only 1 and 5 evenly divide it, whereas 6 is composite
because it has the divisors 2 and 3 in addition to 1 and 6. The fundamental
theorem of arithmetic establishes the central role of primes in number
theory: any integer greater than 1 can be expressed as a product of primes
that is unique up to ordering. The uniqueness in this theorem requires
excluding 1 as a prime because one can include arbitrarily many copies of 1
in any factorization, e.g., 3, 1 Ã 3, 1 Ã 1 Ã 3, etc. are all
valid factorizations of 3.

The property of being prime is called primality. A simple but slow method
of verifying the primality of a given number /n/ is known as trial
division. It consists of testing whether /n/ is a multiple of any integer
between 2 and \sqrt{n}. Algorithms that are much more efficient than trial
division have been devised to test the primality of large numbers.
Particularly fast methods are available for numbers of special forms, such
as Mersenne numbers. As of February 2013^[update], the largest known prime
number has 17,425,170 decimal digits.

There are infinitely many primes, as demonstrated by Euclid around 300 BC.
There is no known useful formula that sets apart all of the prime numbers
from composites. However, the distribution of primes, that