DSA Notes

Math

Primes & Divisors

Read a number through its prime factors, and look for what never changes.

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 long for p * 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.
Watch it run

Practise on LeetCode