A prime number is defined by divisibility, but a good primality algorithm does not necessarily try every possible divisor.
This distinction is one of the most important lessons in computational number theory. To prove that a number is composite, one factor is enough. To prove that it is prime, brute-force trial division is possible but may become inefficient. Modern algorithms instead exploit the arithmetic behaviour that every prime must satisfy and ask whether the candidate behaves like a prime under carefully chosen tests.
This guide separates four different jobs that are often mixed together: generating many primes up to a bound, checking one candidate by trial division, running fast probable-prime tests, and understanding what stronger evidence is needed when a formal primality proof is required.
This is Guide 3 in the Bukit Timah Tutor Computational Number Theory series. Use the BTT Mathematics Hub for the wider Mathematics route.
Generate → screen → test → certify → verify.
1. Prime, composite and unit
A positive integer p>1 is prime if its only positive divisors are 1 and p. A positive integer n>1 that is not prime is composite. The integer 1 is neither prime nor composite.
That final convention matters algorithmically. Code that labels 1 as prime will contaminate every later prime-generation or factorisation routine that depends on it.
2. Why checking divisors only up to √n is enough
If n is composite, write n=ab with 1<a≤b<n. Then a²≤ab=n, so a≤√n. Therefore every composite n has a nontrivial factor no larger than √n.
This gives the standard trial-division test:
is_prime_trial(n):
if n < 2: return false
if n = 2: return true
if n is even: return false
d = 3
while d·d ≤ n:
if n mod d = 0: return false
d = d + 2
return true
The test is exact. Its weakness is cost: the number of candidate divisors grows roughly like √n, which is exponential in half the bit length of n. For modest integers this is perfectly useful; for very large integers it is not the final algorithm we want.
3. Trial division should use primes, not every odd number
If a composite divisor d divides n, then some prime factor of d also divides n. Therefore once a list of primes is available, trial division needs to test only prime divisors up to √n.
This already suggests a useful division of labour: when many candidates must be checked in the same range, generate small primes once and reuse them.
4. The Sieve of Eratosthenes
The Sieve of Eratosthenes generates every prime up to a chosen bound N.
sieve(N):
mark 0 and 1 as composite
mark 2..N as potentially prime
for p from 2 while p·p ≤ N:
if p is still marked prime:
mark p², p²+p, p²+2p, ... ≤ N as composite
return all unmarked integers ≥ 2
Why start crossing out at p²? Smaller multiples 2p,3p,…,(p−1)p already have a factor smaller than p and were therefore crossed out by an earlier prime.
Example: primes up to 30
Start with 2 through 30. Keep 2 and remove its multiples greater than 2. Keep 3 and remove its surviving multiples from 9 onward. Keep 5 and begin at 25. Since the next prime 7 has 7²>30, the crossing-out stage is complete.
The remaining primes are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
5. Why the sieve is efficient
A naive view says that many multiples are crossed out, so the sieve must be expensive. The aggregate number of marking operations is governed by the reciprocal sum over primes. The resulting running time is O(N log log N) under the usual arithmetic model, with O(N) memory for the direct boolean-array implementation.
The point is practical as well as theoretical: when the job is “list all primes up to N,” a sieve is usually much more appropriate than calling an independent primality test on every integer.
6. Simple sieve refinements
- Ignore even candidates after 2. Store only odd numbers and cut memory roughly in half.
- Use compact bit storage. A bitset can greatly reduce memory compared with general-purpose boolean objects.
- Stop the crossing prime at √N. Larger primes do not generate a first unmarked composite within the range.
- Use wheel ideas. Skip residues divisible by several small primes when the added implementation complexity is justified.
7. Segmented sieve: prime generation without storing the whole interval
Suppose we want primes in a large interval [L,R], but storing a boolean array all the way from 0 to R is undesirable. A segmented sieve separates the problem.
- Generate the primes up to √R with an ordinary sieve.
- Create a marking array only for the current segment [L,R] or for a smaller block inside it.
- For each small prime p, find the first multiple of p inside the segment, but do not mark p itself if it lies in the segment.
- Cross out the multiples of p in that block.
- The unmarked integers greater than 1 are prime.
The segmented approach changes the memory profile while preserving the same divisibility logic. It is especially useful when the interval is high but not excessively wide.
8. Sieve versus primality test
These are different jobs.
- Sieve: “Give me many or all primes in a bounded interval.”
- Primality test: “Tell me whether this particular large integer is prime.”
A good algorithm starts by identifying which job is actually being asked. Using a sieve to test one enormous isolated integer is wasteful. Running a heavyweight primality test on every small integer up to a moderate bound is also wasteful.
9. Fermat’s little theorem becomes a primality filter
If p is prime and gcd(a,p)=1, Fermat’s little theorem says
a^(p−1) ≡ 1 (mod p).
This creates a one-sided test. If a^(n−1) is not congruent to 1 modulo n for a base a coprime to n, then n is definitely composite.
But if the congruence does hold, n is not necessarily prime. It is only a probable prime to base a.
10. Fermat pseudoprimes
A composite number can pass Fermat’s congruence for some bases. Such a number is called a Fermat pseudoprime to those bases.
The classic example 341=11·31 satisfies 2^340≡1 (mod 341), so a base-2 Fermat test would fail to expose its compositeness.
Worse, Carmichael numbers are composite integers that satisfy a^(n−1)≡1 (mod n) for every base a coprime to n. The smallest is 561=3·11·17.
Passing a necessary condition is not the same as proving the defining property.
11. From Fermat to Miller–Rabin
The Miller–Rabin test strengthens Fermat’s idea by examining the chain of repeated squarings that leads to a^(n−1).
For an odd candidate n>2, write
n−1 = 2^s d with d odd.
For a chosen base a with 2≤a≤n−2, compute x=a^d mod n. The candidate passes this base if either:
- x=1, or
- one of x, x², x^4, …, x^(2^(s−1)) is congruent to −1 modulo n.
If neither happens, a is a witness to compositeness.
12. Why the −1 condition appears
For a prime p, the only solutions of y²≡1 (mod p) are y≡±1. This follows because p divides (y−1)(y+1), and a prime dividing a product must divide one factor.
Now examine the squaring chain from a^d to a^(2^s d)=a^(p−1)≡1. If the chain does not begin at 1, then before it first reaches 1 it must pass through −1. A nontrivial square root of 1 would contradict primality.
Miller–Rabin therefore inspects more structure than the final Fermat residue alone.
13. Worked Miller–Rabin example: n=221
We know 221=13·17, but pretend we do not. Since 220=4·55, we have s=2 and d=55.
Choose base a=2. Fast modular exponentiation gives
x = 2^55 mod 221 = 128.
This is neither 1 nor −1≡220. Square once because s−1=1:
128² mod 221 = 30.
Again the result is not 220. Therefore base 2 is a Miller–Rabin witness and 221 is composite.
We did not find the factors 13 and 17. We did not need to. This is the crucial separation between detecting compositeness and factoring.
14. Miller–Rabin pseudocode
miller_rabin_round(n, a):
write n−1 = 2^s d with d odd
x = a^d mod n
if x = 1 or x = n−1:
return "passes this base"
repeat s−1 times:
x = x² mod n
if x = n−1:
return "passes this base"
return "composite"
Before running rounds, implementations normally handle n<2, small primes and even n separately. Small-prime trial division is also a cheap screen before more expensive modular exponentiation.
15. What “probable prime” means
If an odd composite n is tested with a uniformly random admissible Miller–Rabin base, at most one quarter of the bases can be strong liars. Therefore a composite number surviving k independent random rounds has probability at most 4^(−k) of having survived all rounds under the random-base model.
This does not mean a tested number is “75% prime.” Primality is not probabilistic: n is either prime or composite. The probability belongs to the testing procedure’s chance of failing to expose a composite input under its random choices.
16. Deterministic Miller–Rabin for bounded integers
For integers restricted to a fixed machine range, carefully chosen finite base sets can make Miller–Rabin deterministic: every composite number in that bounded range is caught by at least one base in the set.
The exact base set depends on the numerical bound. That detail should be treated as part of the implementation specification, not copied casually from a different integer range.
For arbitrary-size integers, randomized Miller–Rabin remains a standard fast screening tool, often followed by stronger certification when an actual proof is required.
17. Primality testing is easier than integer factorisation
This is a profound computational asymmetry. To determine that n is prime, we do not have to search exhaustively for a factor. There are deterministic polynomial-time primality algorithms, most famously AKS, which established that primality belongs to the complexity class P.
That theoretical result does not make AKS the default practical test for ordinary software. Fast probabilistic tests and specialised proving methods are generally preferable in practice. But the conceptual conclusion is decisive:
“Is n prime?” and “What are the prime factors of n?” are different computational problems.
18. Certificates and proofs of primality
A probable-prime test gives very strong evidence. A primality proof gives a verifiable certificate or argument establishing that no composite interpretation remains.
Different proving approaches exploit different structure. Classical criteria may use partial or complete factorisation of n−1 or n+1. Modern elliptic-curve primality proving methods can produce certificates for very large inputs. The verification stage is often substantially cheaper than discovering the certificate.
This returns us to a recurring algorithmic pattern: search may be hard; verification may be easier.
19. Searching for a prime
Suppose an application needs a prime near a certain size. A practical pipeline might be:
- Generate a candidate of the required size.
- Reject impossible forms immediately: even numbers, numbers ending in 5 when decimal size exceeds one digit, and so on.
- Trial-divide by a table of small primes.
- Run several Miller–Rabin rounds or an appropriate deterministic bounded-range version.
- If proof is required, run a primality-proving procedure and retain its certificate.
Each stage is cheaper than the next and removes easy failures early. This layered design is common far beyond number theory.
20. Prime density and why random search is workable
The prime number theorem says that primes near a large number x have density roughly 1/ln x. So a random integer near x has probability about 1/ln x of being prime, while a random odd integer has approximately twice that chance because even composites have already been removed.
Primes become sparser, but not so sparse that searching by testing nearby candidates becomes unreasonable. This statistical fact supports many practical prime-generation strategies.
21. Common mistakes
- Treating 1 as prime. It is neither prime nor composite.
- Trial-dividing past √n. No new first factor can appear beyond the square root.
- Using a sieve for one isolated giant integer. The job does not match the tool.
- Calling a Fermat pass a proof. Pseudoprimes and Carmichael numbers exist.
- Calling a Miller–Rabin pass “definitely prime” without qualification. Random rounds produce probable-prime evidence unless the chosen bounded-range base theorem applies.
- Forgetting small cases. n=2 and n=3 need deliberate treatment; even n>2 are composite.
- Computing powers directly. Every primality test based on a^e mod n should use fast modular exponentiation.
- Confusing compositeness detection with factorisation. A witness may prove n composite without revealing a factor.
22. Practice set
- List all primes up to 50 using a sieve.
- Explain why crossing out multiples of p can begin at p².
- Use trial division to determine whether 221 is prime.
- Determine whether 97 is prime by trial division.
- Show that 341 is composite.
- Why does passing base-2 Fermat not prove that 341 is prime?
- For n=91, write n−1=2^s d with d odd.
- For n=221 and base 2, identify the Miller–Rabin values that expose compositeness.
- Explain the difference between a prime sieve and a primality test.
- Why is √n trial division not polynomial in the bit length of n?
- What does “probable prime” mean in a randomized test?
- Why can a primality certificate be useful even after a trusted program has declared a number prime?
23. Answers and checks
1. 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.
2. Any smaller multiple kp with 2≤k<p already has a factor k<p and has been handled by an earlier prime factor.
3. √221 is less than 15. Test primes 2,3,5,7,11,13; 13 divides 221, so 221 is composite.
4. √97<10. Test 2,3,5,7. None divides 97, so 97 is prime.
5. 341=11·31.
6. The Fermat condition is necessary for primes but not sufficient; 341 is a base-2 pseudoprime.
7. 90=2·45, so s=1,d=45.
8. n−1=4·55. The first residue is 2^55 mod 221=128; squaring gives 30, never −1≡220 before the allowed chain ends. Thus 2 is a witness.
9. A sieve generates many primes in a range; a primality test classifies a specific candidate.
10. If n has k bits, then n is about 2^k and √n about 2^(k/2), which grows exponentially in k.
11. The number passed a test whose false-prime probability for composite inputs is controlled by the test’s random choices; the number itself is not probabilistically prime.
12. A certificate makes the conclusion independently checkable and separates trust in the result from trust in one execution environment.
24. The algorithmic lesson
Prime computation illustrates how one mathematical definition can support several very different algorithms.
- Trial division follows the definition directly.
- A sieve exploits shared structure across a whole interval.
- Fermat testing turns a theorem into a fast compositeness filter.
- Miller–Rabin inspects a stronger chain of modular constraints.
- Primality proving adds a certificate when probability is not enough.
The next guide turns to the harder inverse question: once an integer is known to be composite, how can we actually find its factors, and why do some composites resist our algorithms much more strongly than others?
25. Continue the series
- Guide 1: Euclidean Algorithm, Bézout Identity and Modular Inverses
- Guide 2: Fast Modular Exponentiation and the Chinese Remainder Theorem
- Guide 3: Prime Sieves, Probable Primes and Primality Testing
- Guide 4: Integer Factorisation and Computational Limits
Return to the Singapore Mathematics Hub for the wider BTT Mathematics library.