Easy · Divisor Pairing
Understand → Visualise → Practice.
Return how many positive integers divide n exactly.
If d divides n, so does n / d, and one of the two is at most √n. Test d up to √n and count two divisors per hit, or one when d × d = n.
Try d = 1, 2, … while d × d ≤ n.
If n % d == 0, count d and n / d: add 2, or 1 when d × d == n.
Every divisor has been counted exactly once.
O(√n) time and O(1) space.
A perfect square's root pairs with itself; counting it twice overcounts by one.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.