Prime Factorization
Divide out each candidate while it divides. Whatever is left above 1 is prime.
Result · step 7 of 8Number Theory Basics: Prime factors of 360
Nothing up to the square root divides 5, so 5 is prime itself. It is the last factor.
What you will see
n shrinks as factors peel off into a growing list.
Cost
| Best | O(log n) |
|---|---|
| Average | O(sqrt(n)) |
| Worst | O(sqrt(n)) |
| Space | O(log n) |
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
Taught by the same lesson
Number Theory Basics covers these too, in the same run.