Divisor Functions — d(n), σ(n) & the Divisor Sieve
From the prime factorization, d(n) = Π(aᵢ+1) and σ(n) = Π(1+p+…+p^a). The divisor sieve computes both for all numbers up to N by striding each divisor through its multiples — Σ N/d ≈ N ln N.
step 0
Prime-power blocks of n = 360
d(n) = ? σ(n) = ?
active prime power contributes (a+1) to d contributes geom. sum to σ
Running product
prime p—
exponent a—
d ×= (a+1)1
σ ×= 1+…+p^a1
Complexity
Operation
Time
Factor n (trial division)
O(√n)
d(n) from exponents
O(#primes)
σ(n) from exponents
O(Σ aᵢ)
Press Step. We factor n into prime powers, then fold each block into the product: every prime power multiplies d by (a+1) and σ by (1 + p + … + p^a).
step 0
Numbers 1 … 20 (top = d(m), bottom = σ(m))
being struck by divisor d received a divisord count σ sum
State
current divisor d—
striking m—
m gets d(m)++—
m gets σ(m)+=d—
total strikes0
Complexity
Operation
Time
Divisor sieve (all m ≤ N)
O(N log N)
Linear sieve (all m ≤ N)
O(N)
Query d(m)/σ(m) after
O(1)
Space
O(N)
Press Step. For each divisor d = 1, 2, 3, …, we stride through its multiples d, 2d, 3d, …, adding 1 to each multiple's divisor count and adding d to its divisor sum.
Self-contained visualization. Left tab: the closed forms d(n)=Π(aᵢ+1) and σ(n)=Π(1+p+…+p^a) from the factorization (multiplicativity over coprime prime powers). Right tab: the divisor sieve, whose total work Σ₃≤ₙ N/d ≈ N ln N gives O(N log N). See junior.md, middle.md, and professional.md for derivations and the linear-sieve O(N) variant.