Divisor Functions

${\sigma }_k(n)={\sum }_{d\mid n}{d}^k.$

Two special cases dominate:

• $d(n)={\sigma }_0(n)$ — the number of divisors,
• $\sigma (n)={\sigma }_1(n)$ — the sum of divisors.

From the factorisation

For $n=\prod p_i^{e_i}$:

$d(n)=\prod (e_i+1),\sigma (n)=\prod \frac{p_i^{e_i+1}-1}{p_i-1},{\sigma }_k(n)=\prod \frac{p_i^{k(e_i+1)}-1}{p_i^k-1}.$

All are multiplicative.

Computing for all $n\le N$

The harmonic-series sieve — $O(N\log N)$:

vector<int> d(N + 1, 0);
for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i) d[j]++;          // count of divisors
 
vector<long long> sig(N + 1, 0);
for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i) sig[j] += i;     // sum of divisors

The total work is ${\sum }_{i=1}^{N}N/i\approx N\ln N$. This “iterate over multiples of each $i$” pattern is the single most useful loop in divisor problems.

For $O(N)$, use a linear sieve tracking the exponent of the smallest prime factor.

Enumerating the divisors of one $n$

vector<long long> divisors(long long n) {
    vector<long long> d;
    for (long long i = 1; i * i <= n; i++)
        if (n % i == 0) { d.push_back(i); if (i != n / i) d.push_back(n / i); }
    sort(d.begin(), d.end());
    return d;
}

$O(\sqrt{n})$. For $n$ up to $10^{18}$, factor first and generate divisors from the exponent vectors — $O(d(n))$ after factorisation.

Size bounds

$n$	max $d(n)$	achieved at
$10^3$	32	840
$10^6$	240	720 720
$10^9$	1344	735 134 400
$10^{12}$	6720
$10^{18}$	103 680

Average: $\frac{1}{N}{\sum }_{n\le N}d(n)\approx \ln N$. So “loop over all divisors of every $n\le N$” is $O(N\log N)$, not $O(N\sqrt{N})$.

Related quantities

Function	Meaning
$d(n)$	number of divisors
$\sigma (n)$	sum of divisors
$s(n)=\sigma (n)-n$	aliquot sum — sum of proper divisors
$\omega (n)$	number of distinct prime factors
$\Omega (n)$	number of prime factors with multiplicity
$\mathrm{rad}(n)$	product of distinct primes

Perfect numbers satisfy $\sigma (n)=2n$ (equivalently $s(n)=n$): 6, 28, 496, 8128. Every even perfect number is $2^{p-1}(2^p-1)$ with $2^p-1$ a Mersenne prime (Euclid-Euler). Whether an odd perfect number exists is a famous open problem.

Amicable pairs satisfy $s(a)=b$ and $s(b)=a$: (220, 284).

Useful identities

${\sum }_{d\mid n}d(d)={\left({\sum }_{d\mid n}1\right)}^{?}\text{— no; but:}{\sum }_{n\le N}d(n)={\sum }_{i\le N}\lfloor \frac{N}{i}\rfloor .$

That last identity is the workhorse: the number of pairs $(i,j)$ with $ij\le N$ equals ${\sum }_{n\le N}d(n)$, computable in $O(\sqrt{N})$ with the Dirichlet hyperbola method:

${\sum }_{n\le N}d(n)=2{\sum }_{i\le \sqrt{N}}\lfloor \frac{N}{i}\rfloor -\lfloor \sqrt{N}{\rfloor }^2.$

The same method computes $\sum \sigma (n)$ and other divisor-convolution sums in $O(\sqrt{N})$.

Problem patterns

Problem	Approach
Count numbers $\le N$ with exactly $k$ divisors	sieve $d$, then count
Smallest number with $\ge k$ divisors	search over exponent patterns of the first primes
${\sum }_{n\le N}d(n)$ for $N\le 10^{12}$	hyperbola method, $O(\sqrt{N})$
Divisors of $n!$	Legendre’s formula per prime
Number of divisors of a product	factor each, add exponents
Sum over $(i,j)$ with $i\mid j$	iterate multiples, $O(N\log N)$
Highly composite numbers	recursive search over non-increasing exponents

The multiples loop is not $O(N^2)$

Beginners often avoid for i, for j += i fearing quadratic cost. It is $O(N\log N)$ — for $N=10^6$ that is $1.4\cdot 10^7$ operations, entirely affordable. Recognising this unlocks a large class of otherwise-hard problems.

See also: Integer Factorization · Möbius Function · Sieve Techniques