Bruno Prime — Prime numbers as a working topic: how | brunoprime.com
Four methods in order of increasing power, each with the exact steps and the cases where it fails.
Trial division is the baseline: reject n below 2, divide by 2 and 3, then test candidates up to √n. It is exact but grows expensive quickly, since the candidate count scales with the square root of n.
The 6k ± 1 wheel refines trial division by noting that every integer greater than 3 is congruent to one of six residues, and only two of them — 6k − 1 and 6k + 1 — can be prime. Removing multiples of 2 and 3 deletes two thirds of the candidates before any division runs.
The Fermat test checks whether a^(n−1) ≡ 1 (mod n) for a chosen base a. It is fast, but some composite numbers — the Fermat pseudoprimes — satisfy the congruence for every base coprime to them, so a pass does not prove primality.
On narrow screens, swipe or scroll the plate sideways.
Miller-Rabin strengthens Fermat by factoring n − 1 as 2^s · d and demanding a specific square-root structure. Below 3.3 × 10^24 a fixed set of small bases makes the test deterministic; above that bound it is probabilistic, with each additional base halving the chance of a false positive.
Failure cases differ by method. Trial division never fails, it only slows down. Fermat can be fooled by Carmichael numbers. Miller-Rabin above its deterministic range can pass a strong pseudoprime, though the probability drops exponentially with each round.
For everyday use: trial division or the 6k ± 1 wheel for numbers up to about 10^12, Miller-Rabin with several bases for anything larger.
Further reading