Primality Test
Try each divisor up to the square root. No hit means prime.
Decision · step 2 of 10Number Theory Basics: Is 97 prime?
97 mod 2 = 1, not zero. 2 is not a factor.
What you will see
Candidate divisors walk up to sqrt(n); a hit marks composite.
Cost
| Best | O(1) |
|---|---|
| Average | O(sqrt(n)) |
| Worst | O(sqrt(n)) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, run it on your own input.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.
Before this
Variants
- Trial Division Deterministic
- Miller-Rabin Probabilistic
Taught by the same lesson
Number Theory Basics covers these too, in the same run.