Prime numbers

Published junio 10, 2026 · By NumberWiki

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The primes — 2, 3, 5, 7, 11, 13, 17, 19, 23, … — are the atoms of arithmetic: every other whole number is built by multiplying them together, in exactly one way. That single fact makes primes the most important objects in all of number theory.

The definition, and why 1 isn't prime

Formally, an integer p > 1 is prime if its only positive divisors are 1 and p. A number greater than 1 that is not prime is composite — it can be written as a product of two smaller positive integers. So 12 is composite (it equals 3 × 4), while 13 is prime (nothing but 1 and 13 divides it).

The number 1 is deliberately excluded from the primes. This isn't an arbitrary choice — it's what makes the rest of arithmetic tidy. If 1 counted as prime, then a number like 12 would have infinitely many "prime factorizations" (2 × 2 × 3, but also 1 × 2 × 2 × 3, and 1 × 1 × 2 × 2 × 3, …), and the uniqueness that the whole subject depends on would collapse. Treating 1 as a unit rather than a prime keeps factorizations unique. For the same reason 0 is neither prime nor composite.

The fundamental theorem of arithmetic

The reason primes matter so much is a result so central it is called the fundamental theorem of arithmetic: every integer greater than 1 is either prime or can be written as a product of primes, and that product is unique apart from the order of the factors. There is one and only one way to break a number into primes.

So 60 is always 2² × 3 × 5 — no other combination of primes multiplies to 60. This uniqueness is what lets us reason about divisibility, greatest common divisors, fractions in lowest terms, and modular arithmetic at all. Every number page on this site shows this prime factorization near the top; it is, in a real sense, the number's DNA.

There are infinitely many primes

Around 300 BCE, Euclid proved in his Elements that the primes never run out — one of the oldest theorems still taught essentially unchanged. His argument is a model of elegance. Suppose you had a complete finite list of all primes. Multiply them all together and add 1. The resulting number leaves a remainder of 1 when divided by every prime on your list, so none of them divides it — which means either it is itself a new prime, or it has a prime factor you missed. Either way your "complete" list was incomplete. No finite list can contain them all, so there are infinitely many primes.

Although primes are infinite, they thin out as you go. The prime number theorem, proved in 1896, makes this precise: the number of primes below n is approximately n ⁄ ln n. Near one million, roughly 1 in every 14 numbers is prime; near one trillion, only about 1 in 27. The primes get sparser, but they never stop.

How do you test whether a number is prime?

The schoolbook method is trial division: to check whether n is prime, try dividing it by every integer from 2 up to √n. If none divides evenly, n is prime. You only need to go as far as the square root, because if n had a factor larger than √n it would also have to have a matching factor smaller than √n, which you'd have already found. Trial division is simple and works fine for small numbers, but it becomes hopelessly slow for the large numbers used in cryptography.

For larger numbers, mathematicians use probabilistic and deterministic primality tests that are vastly faster. The Miller–Rabin test can certify primality with overwhelming confidence in a tiny fraction of the time, and with a fixed set of witness values it becomes a guaranteed-correct test for every 64-bit integer — which is exactly how NumberWiki decides primality on every page. In 2002 the AKS algorithm proved that primality can be tested in polynomial time in general, settling a long-standing theoretical question, though Miller–Rabin remains the practical workhorse.

The sieve of Eratosthenes

To find all the primes up to some limit at once, the classic tool is the sieve of Eratosthenes, named for the Greek mathematician who ran the Library of Alexandria in the third century BCE. Write out every number from 2 to your limit. Circle 2, then cross out all its multiples. Circle the next uncrossed number (3) and cross out all of its multiples. Repeat. The numbers that survive uncrossed are exactly the primes. It's over two thousand years old and still essentially how primes are enumerated in bulk today.

Families of primes

Number theorists track many special families of primes, several of which NumberWiki tags automatically:

Twin primes — pairs that differ by 2, like (11, 13) or (17, 19). Whether there are infinitely many twin primes is one of the most famous open problems in mathematics. A 2013 breakthrough by Yitang Zhang proved that infinitely many prime pairs differ by some bounded gap, and the bound has since been pushed down dramatically — but the gap of exactly 2 remains unproven.
Mersenne primes — primes one less than a power of two, of the form 2^p − 1, such as 3, 7, 31, and 127. The largest known prime is almost always a Mersenne prime, because there is a specially efficient test (the Lucas–Lehmer test) for them. The Great Internet Mersenne Prime Search (GIMPS) has found the record-holders for decades.
Sophie Germain primes — a prime p where 2p + 1 is also prime; important in cryptography and in the history of Fermat's Last Theorem.
Palindromic and other digit-pattern primes — primes that read the same backwards, or that have other base-10 curiosities. These are recreational rather than deep, but they're fun, and the site flags them.

Goldbach's conjecture and other open problems

Despite their simple definition, primes hide some of the hardest unsolved problems in mathematics. Goldbach's conjecture (1742) asserts that every even number greater than 2 is the sum of two primes — verified by computer for every even number into the hundreds of quintillions, yet still unproven in general. Every even-number page on this site shows a Goldbach decomposition. The Riemann hypothesis, about the deep distribution of the primes, carries a million-dollar prize and is widely regarded as the most important open problem in all of mathematics. The twin prime conjecture, mentioned above, is a third. That such elementary questions remain open after centuries is a large part of the primes' enduring fascination.

Why primes matter outside mathematics

Primes are not just a curiosity. Modern public-key cryptography — the RSA algorithm that helps secure web traffic, banking, and messaging — rests directly on a striking asymmetry: it is easy to multiply two large primes together, but extraordinarily hard to take the product and recover the original primes. Multiply two 300-digit primes and the result is trivial to compute; factor that 600-digit product back into its primes and the fastest known computers would take longer than the age of the universe. The security of much of the digital world rests on the difficulty of un-multiplying primes.

Primes on NumberWiki

Every number page on this site computes primality deterministically and, for composite numbers, shows the unique prime factorization, the full list of divisors, and factor pairs. Prime pages are tagged prime, and special families get their own tags you can browse — for example Mersenne primes, twin primes, and palindromes. A few primes to explore: 2 (the only even prime), 1729's neighbourhood, the Mersenne prime 8191, and the largest prime below ten thousand, 9973.