Integer Factorization

The decision table

Situation	Method	Cost
$n\le 10^{12}$, one query	trial division to $\sqrt{n}$	$O(\sqrt{n})$
Many queries, all $\le 10^7$	linear sieve for the smallest prime factor	$O(\log n)$ per query
$n\le 2^{64}$	Pollard’s rho + Miller-Rabin	$O(n^{1/4})$
$n$ has a medium factor, up to 60 digits	ECM	$L_p[1/2,\sqrt{2}]$
60-100 digit semiprime	Quadratic sieve	$L_n[1/2,1]$
> 100 digits	GNFS	$L_n[1/3,1.92]$

Trial division

vector<pair<long long,int>> factor(long long n) {
    vector<pair<long long,int>> f;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p) continue;
        int e = 0;
        while (n % p == 0) { n /= p; e++; }
        f.push_back({p, e});
    }
    if (n > 1) f.push_back({n, 1});               // the remaining prime
    return f;
}

The final if is essential: after dividing out everything up to $\sqrt{n}$, whatever is left is a single prime (there can be at most one factor larger than $\sqrt{n}$).

Smallest-prime-factor sieve — for many queries

vector<int> spf(N + 1);
for (int i = 2; i <= N; i++) {
    if (!spf[i]) for (int j = i; j <= N; j += i) if (!spf[j]) spf[j] = i;
}
// factor in O(log n)
while (n > 1) { int p = spf[n]; int e = 0; while (n % p == 0) { n /= p; e++; } f.push_back({p,e}); }

$O(N\log \log N)$ preprocessing, then each factorisation is $O(\log n)$ — the right structure when the problem factors many numbers below $10^7$.

Pollard’s rho + Miller-Rabin — the 64-bit answer

void factorRec(u64 n, map<u64,int>& f) {
    if (n == 1) return;
    if (isPrime(n)) { f[n]++; return; }           // Miller-Rabin
    u64 d = pollard(n);
    factorRec(d, f);
    factorRec(n / d, f);
}

Strip small primes by trial division first (up to a few thousand) — it removes most of the work and avoids rho’s weakness on tiny factors. See Pollard’s Rho.

Expected $O(n^{1/4})$, which factors any 64-bit number in microseconds.

What factorisation unlocks

Once you have $n=\prod p_i^{e_i}$:

Quantity	Formula
Number of divisors $d(n)$	$\prod (e_i+1)$
Sum of divisors $\sigma (n)$	$\prod \frac{p_i^{e_i+1}-1}{p_i-1}$
Euler totient $\phi (n)$	$n\prod \left(1-\frac{1}{p_i}\right)$
Möbius $\mu (n)$	$0$ if any $e_i>1$, else $(-1{)}^{\#\text{primes}}$
All divisors	recursive product over exponents, $d(n)$ of them
Carmichael $\lambda (n)$	lcm of $\lambda (p_i^{e_i})$
Is $n$ a perfect square?	every $e_i$ even
Primitive root existence	$n\in \{1,2,4,p^k,2p^k\}$

Counting and summing divisors without factoring

Number of divisors for every $n\le N$:

for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i) d[j]++;

$O(N\log N)$ — the harmonic series. The same loop with += i computes $\sigma (n)$.

This “for each $i$, loop over its multiples” pattern is the workhorse of divisor problems and is worth recognising: it is $O(N\log N)$, not $O(N^2)$.

Divisor bounds

$n$	max $d(n)$
$10^6$	240
$10^9$	1344
$10^{12}$	6720
$10^{18}$	103 680

So “enumerate all divisors and do something per divisor” is affordable even for $n=10^{18}$, provided you can factor $n$.

Special forms

• $n=a^b$ — check each $b$ from 2 to ${\log }_{2}n$, taking integer roots.
• Difference of squares ($n=x^2-y^2$) — Fermat’s method; fast when $n$‘s factors are close to $\sqrt{n}$, useless otherwise.
• $n=2^{k}m$ — strip powers of two with __builtin_ctzll.
• Factorials and binomials — do not factor the number; use Legendre’s formula for the exponent of $p$ in $n!$.

See also: Pollard’s Rho · Divisor Functions · Sieve Techniques