What Are Prime Numbers?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Primes are the multiplicative building blocks of the integers: every whole number greater than 1 has a prime factorization that is unique apart from the order of its factors.

The First Few Prime Numbers

The first ten prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

There are 25 primes below 100. Written out in full, they are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. The proportion of numbers that are prime then falls gradually, even as the count rises: there are 168 primes below 1,000 and 1,229 primes below 10,000.

Divisors and Composites

The definition rests on the idea of a divisor. An integer d divides n when n can be written as d multiplied by another integer, leaving no remainder. The number 12 has six positive divisors, namely 1, 2, 3, 4, 6 and 12, so it is composite. The number 13 has only 1 and 13, so it is prime.

A useful way to picture the difference is with rectangles. A composite number of objects can be arranged into a rectangular grid in more than one way. Twelve counters can form a 2 by 6 grid or a 3 by 4 grid. Thirteen counters can only form a single row of 13, which is why the primes are sometimes described as the numbers that refuse to be split evenly.

Why 2 Is the Only Even Prime

Two is the smallest prime and the only even one. Every other even number is divisible by 2 in addition to 1 and itself, which gives it at least three divisors and makes it composite. This makes 2 an exception in many statements about primes, and mathematicians sometimes refer to it informally as the oddest prime because so many results have to treat it separately. All primes greater than 2 are odd, and all primes greater than 3 leave a remainder of either 1 or 5 when divided by 6.

Why 1 Is Not a Prime

The p > 1 clause in the modern definition reflects the convention that 1 is not prime, and that convention has not always been standard. Several mathematicians through the nineteenth century treated 1 as prime, and D. N. Lehmer's List of Prime Numbers from 1 to 10,006,721, published in 1914, still listed it that way. The modern convention became universal because including 1 would break the most important result about primes.

If 1 were prime, then 12 could be factored as 2 x 2 x 3, or as 1 x 2 x 2 x 3, or as 1 x 1 x 2 x 2 x 3, and so on without limit. Unique factorization would fail immediately. Excluding 1 preserves the property that each number has exactly one prime factorization. The deeper reason is that 1 is a unit, meaning it has a multiplicative inverse within the integers, and units are treated as a separate category in every number system where factorization is studied.

The Fundamental Theorem of Arithmetic

This theorem states that every integer greater than 1 is either prime or can be written as a product of primes, and that this factorization is unique apart from the order of the factors. For example, 360 factors as 2 x 2 x 2 x 3 x 3 x 5, usually written as 2³ x 3² x 5. No other combination of primes produces 360.

The result was proved in essence by Euclid around 300 BC and stated in its modern form by Gauss in 1801. It is the reason primes occupy a central place in number theory. Questions about divisibility, greatest common divisors, fractions in lowest terms and modular arithmetic all reduce to questions about prime factorizations.

How Many Primes Are There?

There are infinitely many primes. Euclid's proof is short: suppose only finitely many primes existed, multiply them all together, and add 1. The resulting number leaves a remainder of 1 when divided by any prime on the list, so either it is prime itself or it has a prime factor not on the list. Either way the list was incomplete.

Although primes never run out, they become sparser as numbers grow. The Prime Number Theorem, proved in 1896, states that the count of primes below a value n is approximately n / ln(n). Around 1 in 7 numbers near 1,000 is prime, but only about 1 in 21 near one billion. Gaps between consecutive primes can also be made arbitrarily large, since the sequence of numbers from n! + 2 through n! + n is composite throughout.

How to Test Whether a Number Is Prime

• Trial division: Check whether the number is divisible by any integer from 2 up to its square root. Testing beyond the square root is unnecessary, because if a number has a factor larger than its square root it must also have a matching one below. This method is simple but slow for large inputs.
• Sieve of Eratosthenes: To list every prime below a limit, write out all the numbers and repeatedly strike out the multiples of each prime found. Whatever survives is prime. This remains an efficient approach for generating primes in bulk.
• Fermat and Miller-Rabin tests: These use modular arithmetic to detect composites quickly. The usual random-base form of Miller-Rabin is probabilistic, meaning a number that passes several rounds is prime with very high confidence. For bounded ranges, proven fixed base sets make the test deterministic, as this site's checker does below 2⁶⁴.
• AKS algorithm: Published in 2002, this was the first method proved to determine primality in polynomial time with certainty. It is important theoretically but slower than Miller-Rabin in practice.

Each of these is covered in detail in our guide to how to check whether a number is prime.

Named Families of Primes

Certain forms of primes have been studied enough to acquire names. Twin primes are pairs differing by 2, such as 11 and 13 or 41 and 43. Mersenne primes have the form 2^p - 1 and account for nearly all record-sized primes. Fermat primes have the form 2²ⁿ + 1, and only five are known. Sophie Germain primes are those for which 2p + 1 is also prime, a property with applications in cryptography.

Primes Beyond the Integers

The concept generalizes to other number systems, where the answer can change. In the Gaussian integers, which allow numbers of the form a + bi, the number 5 is no longer prime because it factors as (2 + i)(2 - i). The number 3 remains prime in that system. In general, an ordinary prime stays prime among the Gaussian integers only when it leaves a remainder of 3 on division by 4.

Try Checking a Prime

Use our Prime Number Check to test an integer of up to 20,000 digits, or read about the different types of prime numbers.