Stage 2 · Lesson 4 of 6
Factorisation and divisors
Every number splits uniquely into , its , such as 360 = 2^3 * 3^2 * 5. Trial division finds it by dividing by each candidate p while p * p is at most the number, and whatever is left above 1 is one last large prime.
Divisors come in pairs d and x / d, so you can list them all in O(sqrt x). The factorisation tells you a lot: the number of divisors is the product of (exponent + 1), and a number is a perfect square when every exponent is even. For single numbers up to about 10^12, O(sqrt x) is fast.
Common trapforgetting the final check for a leftover prime above the square root, which silently drops a factor.
A question to check yourself, an AI practice session and 1 cheat sheet entry come with the full roadmap. Unlock
Resources for this stage
Start with
- BookFreeCompetitive Programmer's Handbook
Antti Laaksonen · Beginner
Section 1.5 covers the maths basics and Chapter 21 covers number theory, from primes to modular inverses