Prime Number Formula – Primality Testing & Sieve Algorithm
Formal definitions and formulas for prime number testing: trial division, the Sieve of Eratosthenes, and Miller-Rabin. Includes time complexity and worked examples.
Formula
A number n > 1 is prime if and only if it has no integer divisor between 2 and √n (inclusive). The sieve and Miller-Rabin are efficient algorithms derived from this definition.
Variables
| Symbol | Name | Description | Unit |
|---|---|---|---|
| n | Number under test | The integer being tested for primality | — |
| d | Divisor candidate | Integer tested as a potential factor of n | — |
| √n | Square root of n | Upper bound for trial division — no factor above √n is needed | — |
| N | Sieve upper limit | Find all primes up to this value using the sieve | — |
| a | Witness | Base value used in Miller-Rabin modular arithmetic test | — |
How to Use
- Trial division: for each d from 2 to ⌊√n⌋, check if d divides n. If any does, n is composite. Otherwise n is prime.
- Sieve: create a boolean array of size N+1. Mark multiples of each prime p starting at p² as composite, for all p ≤ √N.
- Miller-Rabin: write n−1 = 2ʳ × d. For each witness a, compute a^d mod n and check the Miller-Rabin conditions. If all witnesses pass, n is (deterministically) prime for the chosen witness set.
Examples
1. Is 97 prime? (trial division)
We only need to test divisors up to ⌊√97⌋ = 9.
| d | 97 ÷ d | Divides evenly? |
|---|---|---|
| 2 | 48.5 | No |
| 3 | 32.3… | No |
| 4 | 24.25 | No |
| 5 | 19.4 | No |
| 6 | 16.1… | No |
| 7 | 13.8… | No |
| 8 | 12.125 | No |
| 9 | 10.7… | No |
No divisor found — 97 is prime.
2. Is 91 prime? (composite example)
Test divisors up to ⌊√91⌋ = 9.
7 divides 91 exactly — 91 is composite. Prime factorisation: 7 × 13.
3. Sieve of Eratosthenes up to N = 20
Mark composites by stepping through multiples of each prime up to √20 ≈ 4.4 (so primes 2 and 3).
| Step | Action | Numbers crossed out |
|---|---|---|
| Start | List 2–20 | None |
| p = 2 | Cross multiples of 2 from 4 | 4, 6, 8, 10, 12, 14, 16, 18, 20 |
| p = 3 | Cross multiples of 3 from 9 | 9, 15 |
| p = 5 | 5 > √20, stop | — |
Primes up to 20: 2, 3, 5, 7, 11, 13, 17, 19
4. Miller-Rabin test for n = 341 with witness a = 2
First write n − 1 = 340 = 4 × 85 = 2² × 85, so r = 2 and d = 85.
The sequence 32 → 1 does not contain n−1 = 340, so 341 is composite. (341 = 11 × 31)
Related pages
- Use the Calculator — Interactive calculator for this formula
- Read the Notes — Step-by-step explanation with worked examples