The idea
Every number factors uniquely as n = p₁^k₁ · p₂^k₂ · …. A divisor picks an exponent from 0 to kᵢ for each prime, so the number of divisors is (k₁+1)(k₂+1)…, and the sum of divisors is the product of (1 + p + p² + … + p^k) over the primes.
Trial division finds the factors by testing p up to √n: O(√n).
For “is it possible?” questions, look for an invariant: a quantity, often a parity, that no move can change. If the start and the goal disagree on it, the answer is no without any search.
Sample problem
204. Count Primes ↗ Medium
Return the number of prime numbers that are strictly less than n.
n = 30 output = 10 (2 3 5 7 11 13 17 19 23 29)
Why the solution works
Testing each number for primality separately costs O(n√n). The sieve of Eratosthenes turns the question round: instead of asking what divides x, each prime marks everything it divides.
Go through the numbers in order. A number still unmarked when you reach it has no smaller prime factor, so it is prime; then mark its multiples as composite.
Marking can start at p², because every smaller multiple of p has a prime factor below p and was marked earlier. Every composite number is eventually marked by its smallest prime factor.
Complexity: O(n log log n) time, O(n) memory.
Watch out
- Use
long longforp * p, or the loop condition overflows. - After the loop a prime larger than √n may remain: handle
n > 1. - With a modulus, the closed form
(p^(k+1) − 1)/(p − 1)needs a modular inverse.