Prime Numbers and How to Find Them

Only 25 prime numbers exist below 100, yet primes never stop appearing no matter how far you count. What makes a number prime, and how do you find one without a computer? This guide covers both. You get a fast test for a single number, plus a method over 2,000 years old that finds every prime up to a limit.

What Makes a Number Prime?

A whole number is prime when it is greater than 1 and divides evenly by exactly two numbers: 1 and itself. The numbers 2, 3, 5, 7, and 11 are all prime, because nothing else divides into them without a remainder.

A number with more than two divisors is called composite. Twelve divides by 1, 2, 3, 4, 6, and 12, so it has six divisors and is composite.

Three edge cases trip people up:

• 1 is not prime. It has only one divisor, so it fails the two-divisor rule.
• 2 is the only even prime. Every larger even number also divides by 2.
• 0 and negative numbers are never prime under the standard definition.

Leaving out 1 keeps an important rule working, the fundamental theorem of arithmetic. It says every whole number above 1 breaks into primes in exactly one way. With 1 counted as prime, 6 would have two breakdowns, 2 x 3 and 1 x 2 x 3, and that uniqueness would vanish.

How Do You Test Whether a Number Is Prime?

Divide the number by each prime up to its square root; when none divides evenly, the number is prime. This method is called trial division.

1. Find the square root of the number and round down.
2. List every prime up to that value.
3. Divide the number by each of those primes in turn.
4. Any even division means the number is composite. No even division means it is prime.

Test 97 as an example. Its square root is about 9.8, so only 2, 3, 5, and 7 need checking.

97 is odd, so 2 fails. Its digits add to 16, which 3 does not divide. It ends in 7, so 5 fails. Finally, 97 / 7 is about 13.86, not a whole number, so 97 is prime.

Two quick rules speed up the early checks. A number divides by 3 when its digits sum to a multiple of 3, and by 5 when it ends in 0 or 5.

Some numbers only look prime. 91 is odd, skips the 3 and 5 checks, and still equals 7 x 13. Check every prime on the list, not just the easy ones.

Why Do You Only Check Divisors Up to the Square Root?

Divisors come in pairs that multiply to the number, and one partner in every pair is at most the square root. So a hidden factor always shows up early.

Take 36, whose square root is 6. Its divisor pairs are 1 x 36, 2 x 18, 3 x 12, 4 x 9, and 6 x 6. Every pair has one member of 6 or less.

A composite number therefore reveals a small divisor before you pass its square root. When nothing turns up by then, no divisor exists above it either.

This shortcut saves real work. The square root of 10,007 is about 100.03, so testing it needs only the 25 primes up to 100. None of them divide it, which makes 10,007 prime.

The opposite case shows why you check the whole list. The square root of 9,991 is about 99.95, and the test succeeds only at the last prime: 9,991 = 97 x 103.

Only prime divisors matter. A number that divides by 9 already divides by 3, which you tested earlier.

How Does the Sieve of Eratosthenes Find Every Prime?

The sieve lists every number up to a limit, then crosses out the multiples of each prime; the numbers left standing are prime. It beats one-by-one testing when you want a whole list.

1. Write every whole number from 2 up to your limit.
2. Circle 2, then cross out every multiple of 2 above it: 4, 6, 8, and so on.
3. Move to the next number not crossed out. It is prime, so circle it and cross out its multiples.
4. Stop once the next prime is larger than the square root of your limit. Every number still standing is prime.

Up to 30, the survivors are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The square root of 30 is about 5.5, so the sieve finishes after 2, 3, and 5.

One trick speeds up the crossing out. For each prime, start at its square, because smaller multiples are already gone. For 7, the first new cross-out is 49, since 14, 21, 28, 35, and 42 fell to 2, 3, or 5.

How Common Are Prime Numbers?

Primes thin out as numbers grow: 25 of the first 100 whole numbers are prime, but only 168 of the first 1,000 are. The share keeps falling, yet the list never ends.

The prime number theorem gives a handy rule of thumb. Near a number n, about 1 number in every ln(n) is prime. Near 1,000,000, ln(n) is about 13.8, so roughly 1 number in 14 is prime.

Gaps between primes can stretch as long as you like. The trick uses factorials such as 5! = 120. The numbers 122, 123, 124, and 125 are all composite, because 5! + k divides by k for every k from 2 to 5.

Real gaps show the same thinning. Below 1,000, the longest stretch without a prime runs from 887 to 907, a gap of 20. Close pairs never disappear, though: 8 twin-prime pairs such as 11 and 13 sit below 100.

Why Do Prime Numbers Matter?

Primes are the building blocks of every whole number. Large primes also sit at the heart of RSA encryption, which protects data sent across the internet.

Testing a number answers a yes-or-no question. Breaking a composite number into its primes is a separate job, and the Prime Factorization Calculator handles it along with a divisor count.

RSA relies on a gap between two tasks. Multiplying two large primes takes a computer a fraction of a second. Recovering them from a 2,048-bit product, about 617 digits long, is far beyond any known method on ordinary computers.

Record hunters chase Mersenne primes, written 2^p – 1. The exponent p must be prime, but that alone is not enough.

2^5 – 1 = 31 and 2^7 – 1 = 127 are prime, while 2^11 – 1 = 2,047 = 23 x 89. The Prime Pages tracks the current record holders.

FAQs About Prime Numbers

Sources

This article is general math education on finding and testing prime numbers. Factoring composite numbers is covered by the calculator page. Reviewed for accuracy by Prof. Dr. Khalil Mudassar, PhD. Last updated September 26, 2026.