A prime number is a positive integer greater than 1 with exactly two positive divisors: 1 and itself. That simple rule decides a lot. It tells us at once that 1 is not prime, that 2 stands alone as the only even prime, and that every larger prime must dodge a long list of possible divisors. When mathematicians ask whether a number is prime, they are really asking whether it stays indivisible after every relevant test has been stripped down to its essentials. For a quick practical check, you can also use a prime number checker.
What Counts as a Prime Number
Under the standard definition, primes live inside the positive integers. So negative integers are not treated as prime numbers, and neither are 0 and 1. A composite number, by contrast, has more than two positive divisors. For example, 15 is composite because it is divisible by 1, 3, 5, and 15.
The definition sounds modest, yet it links to much of number theory. Every integer greater than 1 breaks into prime factors, and—aside from order—that factorization is unique. Because of that, primes act as the basic atoms of multiplication. Not poetry. Arithmetic.
Several small facts matter when people test a number for primality:
- 2 is prime.
- Any even integer greater than 2 is composite.
- 1 is neither prime nor composite.
- A divisor pair always comes in matched form: if a divides n, then n/a divides n as well.
Why the Square Root Bound Works
The most useful fact in elementary prime checking is this: if n is composite, then it has a prime divisor no larger than √n. That is why serious trial division never runs all the way to n – 1.
Here is the idea. Suppose n = ab with both a and b greater than 1. If both factors were larger than √n, then their product would be larger than n, which is impossible. So at least one factor must be at most √n. If that smaller factor is not prime, one of its prime divisors is even smaller. Hence a composite number cannot hide all of its prime divisors above the square root.
This is the reason the square root test is not a trick. It is a theorem-based shortcut. Once that point is clear, the whole subject becomes cleaner.
A Small Example of the Bound
Take 221. Its square root is a little under 15. If 221 were composite, some prime divisor would have to appear among 2, 3, 5, 7, 11, or 13. And it does: 13 divides 221, giving 221 = 13 × 17. No larger search is needed.
| Method | Best Use | What It Can Tell You | Main Idea |
|---|---|---|---|
| Trial Division | One small or medium number | Prime or composite | Test divisibility by relevant primes up to √n. |
| 6k ± 1 Filter | Pre-screening candidates | Eliminates many non-primes, not a proof by itself | Every prime above 3 lies in one of the two residue classes 6k – 1 or 6k + 1. |
| Sieve of Eratosthenes | All primes up to a chosen limit | A whole list of primes | Cross out multiples and keep the untouched integers. |
| Fermat Test | Fast screening of large odd numbers | Probable prime or composite | Uses congruences based on Fermat’s little theorem. |
| Miller–Rabin | Modern software and cryptography | Composite or probable prime | Looks for witnesses that expose non-primes very quickly. |
| AKS | Theoretical certainty | Prime or composite | A deterministic polynomial-time test built from polynomial congruences. |
Methods That People Use to Test Primality
Not all prime checks solve the same problem. Some methods decide whether one number is prime. Others find many primes up to a limit. Some prove primality. Others say a number is a probable prime with an error chance so small that software can rely on it.
Trial Division
Trial division is the classical method. A candidate integer is checked against possible divisors, but only up to the square root and, in a refined version, only against prime divisors. For small and medium values, this is still the clearest exact method. It exposes composites fast when they have a small factor, and it proves primality when no such factor exists.
Two small refinements sharpen the method without changing its logic:
- After checking 2, the search can skip all other even numbers.
- After checking 2 and 3, many implementations only test numbers of the form 6k ± 1, because primes larger than 3 must fall into those classes.
The second point is useful, but it does not certify primality. For instance, 25 = 6(4) + 1, yet 25 is composite. So the expression 6k ± 1 is a filter, not a verdict.
The Sieve of Eratosthenes
When the task is not “Is this one number prime?” but rather “Which numbers up to N are prime?”, the Sieve of Eratosthenes is usually the better lens. Instead of testing each number in isolation, the sieve marks multiples of 2, then multiples of 3, then multiples of the next remaining prime, and so on. What survives is the prime list.
That difference matters. Trial division answers a single-number question. The sieve answers a range question. Many articles blur those two jobs; they are not the same job.
Fermat-Based Testing
For large odd integers, pure division becomes slow. That is where modular arithmetic enters. Fermat’s little theorem says that if p is prime and a is not divisible by p, then ap-1 ≡ 1 (mod p). So when a number fails this congruence for a chosen base, it is definitely composite.
Yet there is a catch. Some composite numbers pass Fermat-style checks for certain bases, and Carmichael numbers are the classic example. They can imitate primes well enough to fool a naive Fermat test. Because of that, Fermat testing is better viewed as a screen than as a final certificate.
Miller–Rabin
Miller–Rabin improves the Fermat idea by looking for stronger witnesses to compositeness. In practice, it is one of the main tools behind modern prime generation. If the test declares a number composite, the answer is exact. If the number passes, it is called a probable prime. That phrase has a formal meaning in modern standards: the number is believed to be prime, and the chance of error is negligible when the test is configured well.
A pleasing detail hides here. For any odd composite number, the share of bases that let it slip through a single Miller–Rabin round is at most one quarter. Repeating the test shrinks the failure chance exponentially. So one pass is good; several are far better.
AKS and Deterministic Proofs
The AKS primality test changed the theory of computation because it gave the first deterministic polynomial-time method that always decides primality without relying on randomness. That was a landmark theoretical step. Still, in ordinary software, AKS is rarely the first practical choice for routine testing; methods such as Miller–Rabin and related proving algorithms tend to be more useful in real workloads.
So the landscape splits neatly:
- Elementary exact methods for smaller numbers
- Probabilistic tests for very fast screening of large inputs
- Deterministic proving methods when a proof of primality is required
Worked Examples
Example: 29
The square root of 29 is a little above 5. So only the prime divisors 2, 3, and 5 matter. 29 is odd, its digit sum is 11, and its last digit is neither 0 nor 5. None of those primes divides it. Therefore 29 is prime.
Example: 97
Here the square root is a little below 10. The relevant primes are 2, 3, 5, and 7. Again, no divisor appears: 97 is odd, the digit sum is 16, the last digit is 7, and 97 is not divisible by 7. So 97 is prime.
Example: 221
The square root is below 15, so the prime checks stop at 13. The number is not divisible by 2, 3, 5, 7, or 11. Then 13 appears, and 221 = 13 × 17. This example shows why the square root bound is enough and why a number can look prime for a while, then fail late in the search.
Example: 341
341 is composite because 341 = 11 × 31. It is also famous for another reason: it can pass a Fermat check in base 2. That makes it a useful reminder that probable prime and prime are not interchangeable phrases. Sometimes the distinction is everything.
What Many Short Explanations Leave Out
Prime checking is often taught as if there were a single universal routine. There is not. The right mathematical picture depends on what is being asked.
- One number, exact answer: trial division or another exact test.
- Many numbers in an interval: a sieve-based method.
- Very large candidate numbers: probabilistic tests, often followed by a proving step if the setting demands certainty.
A second omission is the difference between screening and proving. Fermat and Miller–Rabin are excellent at screening. AKS and other proving methods address a different standard: they certify primality.
A third omission is edge cases. They matter more than they seem. Numbers below 2 are not prime. The number 2 is prime. Every other even number is composite. Miss any one of those facts, and an otherwise elegant description starts to wobble.
Prime Checking Inside Number Theory
Primality testing is not an isolated topic. It sits beside factorization, modular arithmetic, congruences, prime-counting functions, and the study of special prime families. Once the basic question “Is n prime?” appears, several related questions follow naturally.
Prime Factorization
If a number is not prime, one may ask how it factors. That is a different task. Primality testing decides whether a number is prime; factorization asks for the prime divisors themselves. The two problems are linked, but they are not identical. A test may prove compositeness without revealing the full factorization.
Coprimes and GCD Ideas
Two integers are coprime when their greatest common divisor is 1. Many primality tests use this language, especially modular tests. A prime number p has the neat property that every integer from 1 to p – 1 is coprime to p. That clean structure is one reason prime moduli behave so well in algebra and cryptography.
Special Prime Families
Some primes are studied because of their form:
- Twin primes: pairs such as 11 and 13, or 17 and 19.
- Mersenne primes: primes of the form 2p – 1, where p is itself prime.
- Fermat primes: numbers of the form 22m + 1 that turn out to be prime.
These families matter because they reveal patterns, exceptions, and open questions. Prime checking often begins with one candidate integer, then expands into these broader structures.
How Primes Thin Out
There are infinitely many primes, yet they become sparser as numbers grow. The prime-counting function π(x) records how many primes are at most x, and the prime number theorem says that π(x) behaves like x / log x for large x. So primes never run out, but they do spread out.
That tension shapes how algorithms are designed. Prime candidates remain abundant enough to find, though not so abundant that a careless search stays fast forever.
Why Cryptography Cares
Modern public-key systems use very large primes because modular arithmetic over prime-related structures behaves predictably. In that setting, software does not test one or two digits. It tests numbers with many digits, often by combining fast probabilistic tests with stricter confirmation when needed.
FAQ
Is 1 a Prime Number?
No. A prime number has exactly two positive divisors, and 1 has only one positive divisor.
Why Does Prime Checking Stop at the Square Root?
If a number is composite, it can be written as a product of two integers greater than 1. At least one of those factors must be less than or equal to the square root, so a smaller divisor must appear there.
Is Every Number of the Form 6k ± 1 Prime?
No. Every prime greater than 3 has that form, but many composite numbers do as well. The pattern is a useful filter, not a proof.
What Is the Difference Between a Prime and a Probable Prime?
A prime has been established as prime. A probable prime has passed one or more probabilistic tests and is believed to be prime with very small error risk, but that wording does not claim a full deterministic proof.
Which Method Fits a List of Numbers up to a Limit?
For a whole interval, the Sieve of Eratosthenes is usually more natural than testing each number one by one.
Why Is 2 the Only Even Prime?
Any even number greater than 2 is divisible by 2 and therefore has at least three positive divisors: 1, 2, and itself.