Sign in to watch this lesson
Algorithms - Bits and Number Theory · 4:03
Number and Sum of Divisors
A divisor of n = p1^e1 * p2^e2 * ... is a choice of exponents, so 60 = 2^2 * 3 * 5 becomes a 3 x 2 x 2 block of 12 cubes, one per divisor, and weighting each cube by its value factors the sum as (1+2+4)(1+3)(1+5) = 168. We turn both formulas into an O(sqrt(n)) trial-division routine, avoid the leftover-prime and overflow traps of the closed form, and fill a whole table of divisor sums by adding every d to its multiples in n ln n steps, measured on this Mac against the linear sieve.
You will learn
- Derive d(n) = product of (e_i + 1) by seeing each divisor as a choice of exponents
- Derive sigma(n) = product of (1 + p_i + ... + p_i^e_i) and its closed form, and explain why both are multiplicative
- Compute d(n) and sigma(n) in O(sqrt(n)) without forgetting the leftover prime or overflowing the closed form
- Build a table of sigma for all n up to 10^7 with the harmonic sieve (n ln n) and compare it with a linear sieve