Primality Test
Try each divisor up to the square root. No hit means prime.
Number Theory Basics: Is 97 prime?
97 mod 2 = 1, not zero. 2 is not a factor.
Cost
- Best
- O(1)
- Average
- O(sqrt(n))
- Worst
- O(sqrt(n))
- Space
- O(1)
Before this
Variants
- Trial Division
- Miller-Rabin
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Number Theory Basics covers these too, in the same run.