How to check prime numbers

A prime number is a natural number greater than 1 whose only divisors are 1 and itself. That definition takes three seconds to state and sits underneath most of modern cryptography, a large slice of number theory, hashing tricks, random-number seeding, and a handful of algorithms that would otherwise be unimplementable. Checking whether a number is prime sounds easy and is easy for small values—but as numbers grow into the dozens of digits, naive approaches become hopelessly slow. Modern primality testing uses probabilistic algorithms like Miller-Rabin to decide “probably prime” in milliseconds for 2,048-bit numbers, which is what makes RSA and related systems practical. This guide covers the definition, trial division, the Sieve of Eratosthenes, Fermat and Miller-Rabin tests, Mersenne primes, and where primes appear in everyday software.

The definition, with edge cases

A prime p is a natural number greater than 1 with exactly two distinct positive divisors: 1 and p. By this definition, 2 is prime (divisors 1 and 2), 3 is prime, 4 is not (1, 2, 4), 5 is prime, and so on. 1 is not prime. Neither are 0 or negative numbers. The exclusion of 1 is a convention that makes the Fundamental Theorem of Arithmetic (unique prime factorization) work cleanly.

Primes under 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Note: 2 is the only even prime.
All other primes are odd.

Trial division

The textbook check: to test whether n is prime, try dividing by every integer from 2 up to √n. If none divide evenly, n is prime. You only need to go up to the square root because any divisor larger than √nmust pair with one smaller than √n.

Is 97 prime?
  √97 ≈ 9.85, so test divisors 2, 3, 5, 7
  97 / 2 = 48.5    no
  97 / 3 = 32.33   no
  97 / 5 = 19.4    no
  97 / 7 = 13.86   no
  → 97 is prime ✓

Optimization: test only 2, then odd numbers 3, 5, 7, 9...

Trial division is O(√n), which is fine for numbers up to maybe 10¹⁴. For 20-digit numbers it’s too slow. For cryptographic 600-digit numbers it’s absurd—you’d wait longer than the age of the universe.

The Sieve of Eratosthenes

When you want all primes below some limit N, trial-dividing each number separately wastes work. The sieve builds them all at once: write out 2 through N, circle 2, cross out every multiple of 2, circle the next unmarked number (3), cross out every multiple of 3, and so on. Whatever’s circled at the end is prime.

Sieve up to 30:
  Start: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  After 2: cross 4,6,8,10,...
  After 3: cross 9,15,21,27
  After 5: cross 25
  Stop at √30 ≈ 5.5

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

The sieve runs in O(N log log N) time and O(N) memory. For N up to 10⁸it’s the right algorithm; beyond that, segmented sieves or specialized tests are better.

Fermat’s little theorem

If p is prime and a is not divisible by p, then ap-1 ≡ 1 (mod p). You can flip this into a probabilistic test: pick a random a, compute an-1 mod n, and if the result isn’t 1, n is definitely composite. Unfortunately, some composites (Carmichael numbers) pass the Fermat test for every a, so this alone isn’t enough.

Miller-Rabin

Miller-Rabin is the workhorse primality test for large numbers. It refines the Fermat test by examining the square root structure of an-1. Each round with a random witness a either proves n composite or says “probably prime.” After k rounds, the probability of wrongly declaring a composite prime drops to at most 4-k. Forty rounds gives you a one-in- 10²⁴ error rate, which is less than the chance of hardware failure.

Deterministic variants

For numbers below certain thresholds, specific small sets of witnesses turn Miller-Rabin into a deterministic test. For n < 3,317,044,064,679,887,385,961,981, testing the first 13 primes as witnesses is provably correct. AKS (2002) was the first fully polynomial-time deterministic primality test, but it’s much slower than Miller-Rabin in practice.

Mersenne primes

A Mersenne number is Mp = 2p − 1. When p itself is prime and Mp is also prime, it’s a Mersenne prime. Examples: 3 (2²−1), 7 (2³−1), 31 (2⁵−1), 127 (2⁷−1). The Great Internet Mersenne Prime Search (GIMPS) hunts for new ones and discovered the largest known prime as of recent years (over 24 million digits). Mersenne primes are tested with the Lucas-Lehmer test, which is specialized for this form.

Why primes matter for cryptography

RSA encryption relies on the fact that multiplying two large primes is cheap but factoring the product back into primes is hard. A 2,048-bit RSA key uses two primes of about 1,024 bits each; finding them takes a few seconds with Miller-Rabin, but factoring their product takes centuries with known algorithms. Elliptic-curve cryptography uses primes to define field arithmetic. Diffie-Hellman uses them to define groups. If large primality testing were slow, modern HTTPS would be slow.

Primes in everyday software

Hash table sizes are often primes to minimize collision patterns. Linear congruential random number generators use primes as moduli. Cuckoo hashing and Bloom filters use multiple hash functions whose properties depend on prime parameters. Database partitioning functions sometimes mod by a prime. If you’ve ever seen array sizes like 997, 10007, or 1000003 in library code, that’s a prime chosen for hash distribution.

The prime counting function

π(N) denotes the number of primes less than or equal to N. The Prime Number Theorem says π(N) ~ N / ln(N). For N = 1,000,000, π(N) = 78,498, close to the prediction 72,382. Primes thin out as numbers grow, but they never stop—Euclid proved there are infinitely many.

Common mistakes

Calling 1 prime. 1 is the multiplicative identity; it has only one divisor. Excluding it is a deliberate choice to make unique factorization work.

Calling 2 composite because it’s even. 2 is the only even prime. All other primes are odd, but 2 itself is prime.

Stopping trial division at n/2 instead of √n. Factors come in pairs around √n. Testing past √n is redundant work; stopping before it misses no factors.

Assuming Fermat test alone is enough. Carmichael numbers (561, 1105, 1729, ...) pass Fermat for every coprime witness. Miller-Rabin fixes this by checking square root structure, which Carmichael numbers cannot fake.

Using a small number of Miller-Rabin rounds for crypto. For general-purpose checking, 20 rounds is overkill. For cryptographic prime generation, use 40+ rounds or deterministic witness sets.

Trusting naive trial division on huge numbers. A 20-digit number has √n near 10¹⁰—roughly 10 billion trial divisions. Miller-Rabin does the same job in milliseconds.

Confusing “probably prime” with “prime.”Probabilistic tests have a tiny but nonzero error rate. For cryptographic use, the error rate is negligible; for mathematical proofs, you need a deterministic test.

Run the numbers

Stop doing trial division by hand; our prime number checker handles both small numbers with trial division and large inputs with Miller-Rabin. Pair it with the average calculator when you’re analyzing the distribution of primes in a range, and the Base64 encoder for the cryptographic adjacent problem of moving large integer values through text protocols.