Trial division tests whether an integer is prime by searching for a divisor between 2 and the square root of the number. If any tested divisor divides the number exactly, the number is composite. If no such divisor exists, the number is prime.
The method is exact. Its main limitation is speed: the amount of testing grows as the number becomes larger. For small integers, classroom work, manual verification, and small-factor screening, trial division remains one of the clearest primality tests.
Trial division rule: for an integer n ≥ 2, test possible divisors only while d² ≤ n. Finding one divisor proves that n is composite. Reaching the end of that range without finding one proves that n is prime.
How the Trial Division Primality Test Works
A prime number has exactly two positive divisors: 1 and itself. Trial division looks for evidence that a third divisor exists.
Suppose the number being tested is n. A basic version starts with 2 and checks:
Does n mod d = 0?
If yes, d divides n exactly and the number is composite. If not, move to the next possible divisor.
The test does not need to continue all the way to n − 1. It can stop once the divisor passes √n. That stopping rule is what makes trial division practical for modest values.
Why Testing Stops at the Square Root
If a composite number can be written as:
n = a × b
then at least one of the two factors must be less than or equal to √n.
If both factors were greater than √n, their product would be greater than n, which is impossible:
a > √n and b > √n would imply a × b > n.
So any composite integer must have a non-trivial factor on or before the square-root boundary. Once every relevant divisor up to that point has failed, there cannot be a hidden factor beyond it without a matching smaller factor that should already have been found.
The Square-Root Boundary Must Be Included
The word equal matters. Consider 289:
√289 = 17
289 = 17 × 17
If a trial division test stopped before checking 17, it could incorrectly classify 289 as prime. The correct condition is therefore:
d ≤ √nd × d ≤ nd < √nThe Basic Algorithm
The simplest form of trial division can be written as:
if n < 2:
return not prime
for d from 2 while d × d <= n:
if n mod d == 0:
return composite
return primeThe expression d × d ≤ n represents the same mathematical boundary as d ≤ √n. It also avoids repeatedly calculating a square root.
For primality testing, the algorithm can stop as soon as it finds one non-trivial divisor. It does not need to find every factor.
Naive and Optimized Trial Division
Testing every integer from 2 through √n works, but many of those tests are unnecessary. Several versions of trial division can produce the same exact result with fewer candidate divisors.
| Strategy | Divisors Tested | Main Benefit | Limitation |
|---|---|---|---|
| Every integer | 2, 3, 4, 5, 6, 7… | Very simple | Tests many unnecessary values |
| Odd divisors | 2, then 3, 5, 7, 9… | Skips all later even values | Still tests odd composite numbers |
| Prime divisors | 2, 3, 5, 7, 11, 13… | Avoids composite divisors | Requires prime divisors to be available |
| 6k ± 1 candidates | 2, 3, then 5, 7, 11, 13… | Skips multiples of 2 and 3 | Still includes composite candidates |
Test 2, Then Skip Even Divisors
Once 2 has been tested, there is no reason to test 4, 6, 8, 10, or any larger even divisor. If an integer greater than 2 were divisible by one of them, it would already be divisible by 2.
A common optimized loop therefore uses:
2, then 3, 5, 7, 9, 11, 13…
This nearly halves the number of divisor candidates compared with checking every integer.
Why Composite Divisors Can Also Be Skipped
If prime divisors are already being tested, testing a composite divisor adds no new information.
Take 15. Since:
15 = 3 × 5
a number divisible by 15 cannot escape all testing by its smaller prime factors. By the time trial division reaches 15, the relevant factor structure would already have been detected through 3 or 5.
This is why a prime-divisor version can test:
2, 3, 5, 7, 11, 13, 17, 19…
instead of every integer. The trade-off is that the program must already know or generate those primes.
The 6k ± 1 Optimization
Every prime greater than 3 has the form:
6k − 1 or 6k + 1
The reason comes from the six possible remainders modulo 6. Integers congruent to 0, 2, or 4 are even. Integers congruent to 3 are divisible by 3. That leaves only remainders 1 and 5 as possible locations for primes greater than 3.
This lets a trial division implementation skip more candidates after checking 2 and 3.
Possible divisors then follow a pattern such as:
5, 7, 11, 13, 17, 19, 23, 25, 29, 31…
6k ± 1 is not a primality test. It only filters out values that are definitely divisible by 2 or 3. For example, 25 has the required form but is composite because 25 = 5².
Example: Testing 173
Consider 173. Its square root is approximately:
√173 ≈ 13.15
Using prime divisors, only 2, 3, 5, 7, 11, and 13 need to be checked.
| Divisor | 173 mod d | Result |
|---|---|---|
| 2 | 1 | Continue |
| 3 | 2 | Continue |
| 5 | 3 | Continue |
| 7 | 5 | Continue |
| 11 | 8 | Continue |
| 13 | 4 | Continue |
The next prime divisor would be 17, but:
17 > √173
No divisor was found within the required range, so 173 is prime.
Example: Testing 187
Now consider 187:
√187 ≈ 13.67
The test begins with the relevant prime divisors:
| Divisor | 187 mod d | Result |
|---|---|---|
| 2 | 1 | Continue |
| 3 | 1 | Continue |
| 5 | 2 | Continue |
| 7 | 5 | Continue |
| 11 | 0 | Stop |
Once 11 divides 187 exactly, the primality question is settled:
187 = 11 × 17
187 is composite. There is no reason to continue testing 13.
Example: A Factor Exactly at √n
Perfect squares show why the square-root endpoint cannot be skipped. For 289:
√289 = 17
The prime divisors up to the boundary are:
2, 3, 5, 7, 11, 13, 17
None of the first six divides 289. The final required test does:
289 mod 17 = 0
289 = 17²
A condition such as d < √n would miss this factor. That small implementation error can cause perfect squares of primes to be labelled incorrectly.
Why Some Composite Numbers Take Longer
Trial division does not spend the same amount of work on every composite number. What matters is where its smallest non-trivial factor appears.
A number divisible by 2, 3, or 5 is rejected almost immediately. A composite number whose smallest factor sits near √n can require nearly as many tests as a prime number of similar size.
For example:
899 = 29 × 31
√899 ≈ 29.98
The smallest factor is 29, very close to the square-root boundary. A prime-divisor trial division test must pass through:
2, 3, 5, 7, 11, 13, 17, 19, 23
before finally reaching 29.
This explains an important performance detail: being composite does not automatically mean a number is cheap to test.
How Much Work Trial Division Requires
The straightforward method may need to inspect divisors up to roughly √n. That gives trial division a natural square-root growth pattern with respect to the value being tested.
For a number near one million, √n is around one thousand. For a number near one trillion, √n is around one million. The number itself grows much faster than its square root, but the search still becomes costly for very large integers.
Optimizations such as skipping even numbers, using prime divisors, or testing 6k ± 1 candidates reduce the number of attempted divisions. They do not remove the underlying square-root limit.
Early exit matters. A composite number with a small factor may be rejected after only a few divisions. A prime number has no such shortcut, so every required candidate up to the boundary must survive.
Trial Division and Factorization Are Different Tasks
A primality test asks whether a non-trivial divisor exists. Factorization asks for the factor structure of the number.
For example, testing 84 for primality can stop immediately:
84 mod 2 = 0
That single result proves 84 is composite.
Finding its complete prime factorization requires more work:
84 = 2² × 3 × 7
Trial division can be extended into a factorization method by repeatedly dividing out discovered factors, but a primality test does not need to do that.
Candidate Reduction in Practice
The difference between trial division variants becomes clearer when the square-root limit contains many possible candidates.
Take 997:
√997 ≈ 31.58
| Method | Candidate Set Through 31 |
|---|---|
| Every integer | 2 through 31 |
| Odd-only | 2, then 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 |
| Prime-only | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 |
| 6k ± 1 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 |
The 6k ± 1 sequence still contains 25, because the pattern identifies possible primes rather than known primes. A stored prime list removes that extra test.
Edge Cases
A correct implementation needs to handle small values before entering its ordinary divisor loop.
| Input | Classification | Reason |
|---|---|---|
| -7 | Not prime | Prime numbers are positive integers greater than 1 |
| 0 | Not prime | Below 2 |
| 1 | Not prime | Has only one positive divisor |
| 2 | Prime | Smallest prime and the only even prime |
| 3 | Prime | No non-trivial divisor exists |
| 4 | Composite | Divisible by 2 |
| 9 | Composite | Divisible by 3 |
| 49 | Composite | 7 = √49 must be tested |
Common Trial Division Errors
Starting with 1
One divides every integer, so it provides no information about primality. Trial division searches for non-trivial divisors and therefore starts at 2.
Stopping Before the Square Root
Using a strict condition such as d² < n can miss numbers whose only relevant factor at the boundary is √n. Prime squares such as 49, 121, and 289 expose this error.
Continuing After a Divisor Is Found
For primality testing, one non-trivial divisor is enough. Continuing may be useful for factorization, but it does not change the prime/composite result.
Assuming Odd Numbers Are Prime
Being odd only rules out divisibility by 2. Numbers such as 9, 15, 21, 25, and 27 are all odd and composite.
Treating 6k ± 1 as Proof of Primality
The form is a candidate filter. Values such as 25, 35, 49, 55, and 65 pass that filter while remaining composite.
Testing Beyond √n
If no divisor exists through the square-root boundary, further testing cannot reveal a new factor pair. Continuing only adds redundant work.
When Trial Division Is Useful
Trial division fits cases where transparency and exact reasoning matter more than handling extremely large integers. It works well for:
- checking small and moderately sized integers;
- showing why a number is prime or composite;
- educational examples where each tested divisor should be visible;
- removing candidates with small factors before a more advanced primality test;
- small programs where simplicity matters more than large-number performance.
It is also useful as a first screening step. A program can divide by a short list of small primes and reject easy composite numbers before applying a method designed for much larger candidates.
When Trial Division Becomes Impractical
The method becomes less attractive as the integer grows. A large prime forces the test to exhaust every required candidate through √n, and a composite number with no small factors may behave almost the same way.
For that reason, large-number software often uses trial division only to remove small factors and then switches to faster primality methods.
This distinction matters because trial division is an exact deterministic method, while some faster tests used on large numbers are probabilistic unless additional conditions or deterministic parameter ranges are used.
Trial Division, Sieves, and Other Primality Tests
These methods solve related but different problems.
| Method | Main Task | Best Fit |
|---|---|---|
| Trial division | Test one integer for divisors | Small values and transparent verification |
| Prime sieve | Generate many primes within a range | Prime lists and repeated range queries |
| Miller–Rabin | Test large primality candidates | Fast large-integer screening |
A sieve is usually the better choice when many primes within an interval are needed. Trial division is more natural when the question concerns one number and the divisor logic itself matters.
Checking a Number Directly
Trial division explains the reasoning behind a prime/composite decision, but individual values can also be tested directly with the Prime Number Checker. The mathematical idea remains the same: a composite number must reveal a valid non-trivial factor, while a prime number has none.
A Compact Trial Division Pattern
1. Reject integers below 2.
2. Handle 2 separately.
3. Reject larger even numbers.
4. Test remaining candidate divisors while d² ≤ n.
5. Stop immediately if n mod d = 0.
6. If the boundary is passed without finding a divisor, the number is prime.
The strength of trial division comes from this square-root argument. The test never has to search the full interval from 2 to n − 1, and each optimization removes candidate divisors without changing the mathematical result. For small numbers, that makes it both an exact test and a clear way to see why a number is prime.