Prime Factorization
Divide out each candidate while it divides. Whatever is left above 1 is prime.
Number Theory Basics: Prime factors of 360
Nothing up to the square root divides 5, so 5 is prime itself. It is the last factor.
Cost
- Best
- O(log n)
- Average
- O(sqrt(n))
- Worst
- O(sqrt(n))
- Space
- O(log n)
Before this
Taught by the same lesson
Number Theory Basics covers these too, in the same run.