Prime Factorisation — 10^9 Calls Killed API

RSA's security depends on one fact: factoring the product of two large primes is computationally hard. The best known classical algorithm (General Number Field Sieve) runs in sub-exponential but super-polynomial time. A 2048-bit RSA modulus would take longer than the age of the universe to factor on current hardware.

For small numbers — up to ~10^12 — trial division works fine. For competitive programming — up to ~10^6 per query — the SPF sieve turns factorization from O(√n) per query to O(log n). Knowing which regime you're in and choosing the right tool is the practical skill.

The real trap? Assuming one algorithm works for all sizes. Engineers waste hours because they don't detect when trial division becomes impractical or when Pollard's rho loops indefinitely on a prime input.

Why Trial Division Kills Your API at Scale

Prime factorization is the decomposition of a composite number into a product of smaller primes, each prime appearing exactly as many times as its multiplicity. The core mechanic is simple: divide the input by the smallest prime (2), then 3, then 5, etc., until the quotient becomes 1. This is the fundamental theorem of arithmetic — every integer greater than 1 has a unique prime factorization.

In practice, the naive trial division runs in O(√n) per number. For a single 10^12 integer, that's up to 10^6 divisions — trivial. But when your API receives 10^9 requests per day, each requiring factorization of numbers up to 10^12, the total operations hit 10^15. That's not just slow; it's a guaranteed timeout and resource exhaustion. Precomputation via a sieve up to √max(n) (e.g., 10^6) reduces each factorization to O(number of prime factors), typically under 10 divisions.

Use prime factorization when you need to compute GCD/LCM, reduce fractions, or solve modular arithmetic problems. In production, it's the foundation for cryptographic key generation (RSA) and hash table sizing. The difference between O(√n) and O(log n) per call determines whether your service stays up or burns CPU.

Trial Division

Check divisibility by all primes up to √n. O(√n) per number. This is the simplest and most intuitive algorithm. For a single n ≤ 10^12, trial division completes in microseconds. But scale it to 10^6 numbers and you're looking at days.

The key optimization: after checking 2, only check odd numbers. That halves the work. For even better performance, precompute a list of primes up to √max_n using a simple sieve, then only divide by those primes.

def prime_factors(n: int) -> dict[int, int]:
    """Returns {prime: exponent} factorization."""
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

print(prime_factors(360))   # {2:3, 3:2, 5:1}
print(prime_factors(1001))  # {7:1, 11:1, 13:1}
print(prime_factors(97))    # {97:1} — prime

Number of Divisors and Sum of Divisors

These formulas are direct consequences of the multiplicative property. For example, τ(360) = τ(2³)τ(3²)τ(5¹) = (3+1)(2+1)(1+1) = 4×3×2 = 24 divisors. The sum σ(360) = (2^(3+1)-1)/(2-1) × (3^(2+1)-1)/(3-1) × (5^(1+1)-1)/(5-1) = (16-1)/1 × (27-1)/2 × (25-1)/4 = 15 × 13 × 6 = 1170.

def num_divisors(n: int) -> int:
    factors = prime_factors(n)
    result = 1
    for exp in factors.values():
        result *= (exp + 1)
    return result

def sum_divisors(n: int) -> int:
    factors = prime_factors(n)
    result = 1
    for p, exp in factors.items():
        result *= (p**(exp+1) - 1) // (p - 1)
    return result

def euler_totient(n: int) -> int:
    factors = prime_factors(n)
    result = n
    for p in factors:
        result -= result // p
    return result

print(num_divisors(360))   # 24
print(sum_divisors(360))   # 1170
print(euler_totient(36))   # 12

Listing All Divisors

To list all divisors, iterate up to √n and collect pairs. Complexity O(√n) – but you can't beat that because output size is O(τ(n)) which is at most O(√n). For n=10^12, τ(n) is at most ~6720, so enumerating divisors is feasible.

The algorithm: for each divisor d ≤ √n, if n % d == 0, add d and n//d. Sort the result at the end.

def all_divisors(n: int) -> list[int]:
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

print(all_divisors(36))  # [1,2,3,4,6,9,12,18,36]
print(len(all_divisors(360)))  # 24

SPF Sieve for Batch Factorization

When factorizing many numbers up to n, precompute the Smallest Prime Factor (SPF) sieve. Each factorization then takes O(log n) instead of O(√n).

Construction: Create an array spf[0..n] filled with 0. For i from 2 to n, if spf[i]==0 (i is prime), set spf[i]=i and for j in range(i*i, n+1, i), if spf[j]==0, set spf[j]=i. Then to factor a number x, repeatedly divide by spf[x] and record the count.

This is the standard for competitive programming and any scenario where you need to factorise a batch of numbers up to ~10^7.

def spf_sieve(n: int) -> list[int]:
    spf = [0] * (n + 1)
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            if i * i <= n:
                for j in range(i * i, n + 1, i):
                    if spf[j] == 0:
                        spf[j] = i
    return spf

def factorize_with_spf(x: int, spf: list[int]) -> dict[int, int]:
    factors = {}
    while x > 1:
        p = spf[x]
        factors[p] = factors.get(p, 0) + 1
        x //= p
    return factors

spf = spf_sieve(100)
print(factorize_with_spf(72, spf))  # {2:3, 3:2}

Pollard's Rho Algorithm for Large Composite Numbers

When n exceeds ~10^12 and you need to factorise a single number, trial division becomes impractical. Pollard's rho is a probabilistic algorithm that finds a non-trivial factor in O(n^(1/4)) expected time.

It works by iterating a pseudo-random function f(x) = (x^2 + c) mod n and detecting cycles using Floyd's cycle detection. When a cycle is found, gcd(|x-y|, n) gives a factor.

It's not guaranteed – for prime n it will loop forever. Always pair it with a primality test (Miller-Rabin) before running rho.

import math

def pollard_rho(n: int) -> int:
    if n % 2 == 0:
        return 2
    c = 1
    x = 2
    y = 2
    d = 1
    while d == 1:
        x = (x * x + c) % n
        y = (y * y + c) % n
        y = (y * y + c) % n
        d = math.gcd(abs(x - y), n)
        if d == n:
            c += 1
            x = 2
            y = 2
            d = 1
    return d

n = 1000000000000000003  # a large semiprime
print(pollard_rho(n))

Factorization Using Trial Division – O(√n) Time and O(log n) Space

Most devs jump straight into trial division because it's the first thing that comes to mind: loop through numbers, check divisibility, collect factors. At scale, this pattern is a production incident waiting to happen. But for small n or one-off computations, you need to know the sharpest version of it. The variant that avoids redundant checks and unnecessary work.

The trick: strip out all factors of 2 first, then check only odd numbers up to √n. This cuts the loop iterations nearly in half. Every time you find a factor, divide the number down aggressively — this shrinks the search space on the fly. If n is still > 2 after the loop, it's a prime factor itself. That handles the edge case where n is prime. The space stays O(log n) because you only store the discovered factors, and the recursion depth is bounded by the number of distinct prime factors.

This isn't going to win any speed contests for batch processing or massive composites. But for a single query where n fits in 32-bit, this is your surgical strike. No sieves, no memory overhead, just clean brute force with a haircut.

// io.thecodeforge — dsa tutorial

import java.util.ArrayList;
import java.util.List;

public class TrialDivisionSolo {
    public static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        if (n % 2 == 0) {
            factors.add(2);
            while (n % 2 == 0) n /= 2;
        }
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 2) factors.add(n);
        return factors;
    }

    public static void main(String[] args) {
        System.out.println(primeFactors(60));
        System.out.println(primeFactors(100));
        System.out.println(primeFactors(97));
    }
}

Sieve of Eratosthenes – Smallest Prime Factor (SPF) for Batch Domination

When you need to factor a hundred thousand numbers in under a second, trial division is going to get you paged at 3 AM. This is where the Smallest Prime Factor sieve becomes your hammer. Precompute the smallest prime divisor for every number up to some limit N in O(N log log N), then each factorization degrades to O(log n) — just walk the chain of divisions.

The idea is dead simple: create an array spf where spf[i] holds the smallest prime that divides i. Initialize by marking spf[i]=i for all i. Then run the sieve: for each prime p, for each multiple m of p, if spf[m] is still m, set it to p. Once built, factoring n is a loop: grab spf[n], record it, divide n by spf[n], repeat until n=1. No division operations at all during factorization — just array lookups and integer division.

Memory is the trade-off. For N=10⁷, that's 40 MB just for the int array. Fine for most servers, but watch your heap. The payoff is batch throughput: you can factor millions of numbers in the time trial division takes for a hundred. This is what every competitive programmer and production batch processor reaches for when latency matters.

// io.thecodeforge — dsa tutorial

public class SpfBatchFactor {
    private final int[] spf;

    public SpfBatchFactor(int limit) {
        spf = new int[limit + 1];
        for (int i = 2; i <= limit; i++) spf[i] = i;
        for (int i = 2; i * i <= limit; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= limit; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
    }

    public void printFactors(int n) {
        while (n > 1) {
            System.out.print(spf[n] + " ");
            n /= spf[n];
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SpfBatchFactor s = new SpfBatchFactor(100);
        s.printFactors(60);
        s.printFactors(98);
        s.printFactors(97);
    }
}

Pollard's Rho – When n Kicks Your Sieve Out of RAM

You've maxed out your SPF sieve at 10⁷ and somebody hands you a 64-bit composite. Trial division would take until retirement. Pollard's Rho is your escape hatch. It's a probabilistic algorithm that finds a non-trivial factor in O(√√n) expected time — that's O(n^¼) for the number crunchers. For a 10¹² number, you're looking at around 10⁶ iterations worst-case. Not free, but survivable.

The core idea is perversely simple: generate a pseudo-random sequence modulo n, look for collisions using Floyd's cycle detection (tortoise and hare). When you detect a cycle, compute gcd(a - b, n). If that gcd is > 1 and < n, you've found a factor. Recursively apply to both halves. Pure Miller-Rabin to test primality of the results. The whole pipeline — Miller-Rabin + Pollard's Rho — is what's behind every serious factorization library.

You don't write this from scratch for production unless you're a masochist. Java's BigInteger doesn't ship with Pollard's Rho. You'll need to roll it or pull in a lib. But understanding it is the difference between "works on my machine" and "works on the customer's 10¹⁸ invoice ID."

// io.thecodeforge — dsa tutorial

import java.math.BigInteger;
import java.security.SecureRandom;

public class PollardRhino {
    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = BigInteger.valueOf(2);
    private static final SecureRandom rng = new SecureRandom();

    public static BigInteger pollardRho(BigInteger n) {
        if (n.mod(TWO).equals(ZERO)) return TWO;
        BigInteger x = new BigInteger(n.bitLength(), rng).mod(n.subtract(ONE)).add(ONE);
        BigInteger c = new BigInteger(n.bitLength(), rng).mod(n.subtract(ONE)).add(ONE);
        BigInteger y = x;
        BigInteger d = ONE;

        while (d.equals(ONE)) {
            x = x.multiply(x).mod(n).add(c).mod(n);
            y = y.multiply(y).mod(n).add(c).mod(n);
            y = y.multiply(y).mod(n).add(c).mod(n);
            d = x.subtract(y).abs().gcd(n);
        }
        return d;
    }

    public static void main(String[] args) {
        BigInteger n = new BigInteger("80538738812075974");
        System.out.println("Factor found: " + pollardRho(n));
    }
}