∑MathIntermediate

Prime Factorization

Key Points

  • •
    Prime factorization expresses any integer greater than 1 as a product of primes raised to powers, uniquely up to ordering.
  • •
    Trial division checks small prime candidates up to \(\), which is simple and fast enough for moderate n.
  • •
    A sieve of smallest prime factor (SPF) precomputes smallest primes for all numbers up to N, enabling \(O( n)\) factorization per query after \(O(N N)\) preprocessing.
  • •
    For 64-bit integers, Miller–Rabin gives a very fast primality test, and Pollard’s Rho finds nontrivial factors in expected \(O()\) time.
  • •
    Once factored as \(n= p_\), many arithmetic functions are easy: number of divisors, sum of divisors, and Euler’s totient have simple formulas.
  • •
    In contests (CF 1200–1700), combine SPF for small/medium inputs and Pollard’s Rho + Miller–Rabin for 64-bit values.
  • •
    Mind overflow: use 128-bit intermediates for modular operations on 64-bit numbers.
  • •
    Choose the right tool: trial for single small n, SPF for many queries, and Rho+MR for large 64-bit n.

Prerequisites

  • →Modular arithmetic — Miller–Rabin and Pollard’s Rho rely on modular multiplication and exponentiation.
  • →Greatest Common Divisor (Euclidean Algorithm) — Pollard’s Rho extracts factors using gcd of differences.
  • →Sieve of Eratosthenes — Understanding sieves helps build SPF for fast multi-query factorization.
  • →Binary exponentiation — Efficient modular exponentiation is essential for primality tests.
  • →Time complexity and Big-O notation — Choosing the right factorization method requires comparing complexities.
  • →Randomized algorithms — Pollard’s Rho uses randomness; understanding expected time and retries is helpful.

Detailed Explanation

Tap terms for definitions

01Overview

Prime factorization is the process of breaking a positive integer n into a product of prime numbers, each possibly repeated. For example, 360 = 2^3 · 3^2 · 5^1. This decomposition is unique up to the order of the factors (the Fundamental Theorem of Arithmetic). Factorization is a cornerstone in number theory and competitive programming because many functions of n (like the number of divisors, the sum of divisors, and Euler’s totient) become easy once you know the primes and their exponents. Practically, we care about efficient ways to factor numbers of different sizes. For small or moderate n, simple trial division up to (\sqrt{n}) works well. For many queries over a bounded range, we can precompute the smallest prime factor (SPF) for every number up to N in nearly linear time; then, each factorization is fast. For large 64-bit integers (like up to 10^{18}), probabilistic-but-reliable methods such as Miller–Rabin primality testing and Pollard’s Rho factorization are used. Choosing the right method depends on n’s size and how many numbers you must factor.

02Intuition & Analogies

Think of n as a pile of identical Lego towers. Each prime is a basic brick type, and stacking e copies of prime p is like building a tower p^e. Factorization asks: which brick types do we have, and how many of each? Trial division is like trying to disassemble the tower by checking small wrenches first: try 2, then 3, then 5, and so on. You only need to try wrenches up to the square root because if no small wrench works, any remaining bolt (factor) must be large and appears at most once. An SPF sieve is like labeling every Lego piece in a warehouse beforehand with its smallest compatible tool; then when you need to disassemble any tower in that warehouse (numbers up to N), you peel off pieces quickly by following those labels. For very large towers, trying every small wrench is too slow. Miller–Rabin acts like a quick authenticity scanner that tells if your piece is prime with extremely high confidence (deterministic for 64-bit with chosen bases). Pollard’s Rho is a clever randomized game: you walk through states using a simple function while periodically taking a GCD of differences; cycles and modular arithmetic make it surprisingly likely you stumble upon a hidden nontrivial factor. Once the bricks and counts are known, many properties (how many distinct reassemblies, total weight, or stability) map directly to divisor-count, sum-of-divisors, or totient formulas.

03Formal Definition

For an integer \(n 2\), prime factorization is the expression \(n = p_\), where each \(\) is prime, \( < < \), and each exponent \( 1\) is an integer. The Fundamental Theorem of Arithmetic states that such a representation exists and is unique up to ordering. Algorithmically, factorization is the problem of computing the set of pairs \(\{(, )\}\). Trial division attempts primes (or integers) up to \( \) and divides out factors when found. An SPF sieve precomputes an array spf[x] giving the smallest prime dividing x for all \(2 x N\); then factorization repeatedly records spf[x] and divides by it until reaching 1, counting multiplicities. Miller–Rabin primality testing decides if a number is likely prime by checking whether certain modular exponentiation identities hold for chosen bases; for 64-bit integers, a fixed small base set yields determinism. Pollard’s Rho uses random polynomial iterations modulo n and the greatest common divisor (GCD) to find a nontrivial divisor with expected sub-exponential time \(O()\) on average for random inputs within 64-bit range.

04When to Use

  • Single small or moderate n (say n ≤ 10^9–10^{12}): trial division with small optimizations (handle 2 separately, check odd numbers, optionally wheel 2·3·5) is often enough. - Many queries with values ≤ N (e.g., factor thousands of numbers each ≤ 10^7): precompute an SPF sieve in (O(N \log \log N)) time and (O(N)) memory; factor each query in (O(\log n)). - Mixed sizes up to 64-bit (≤ 10^{18}): use Miller–Rabin to detect primes quickly and Pollard’s Rho to split composites; fall back to recursion until fully factored. - Need divisor-related functions (number of divisors, sum of divisors, Euler’s totient): factor first, then apply closed-form multiplicative formulas. - Competitive programming at CF 1200–1700: SPF for bounded-range multi-queries, trial division for one-off moderate n, and a ready Pollard’s Rho + Miller–Rabin template for general 64-bit cases give excellent coverage.

⚠️Common Mistakes

  • Forgetting to factor out all copies of a prime: always divide repeatedly while n % p == 0 to collect full exponent. - Looping i up to n instead of up to (\sqrt{n}): this is an unnecessary slowdown; update the loop condition with i * i ≤ n and beware overflow by using i ≤ n / i. - Using int for products/modulo with 64-bit numbers: modular multiplication/exponentiation should use 128-bit intermediates (e.g., __int128 in C++) to avoid overflow. - Treating Miller–Rabin as probabilistic for 64-bit without fixed bases: choose a known deterministic base set for 64-bit (e.g., {2,3,5,7,11,13,17}). - Not handling the leftover prime after trial division: if n > 1 when the loop ends, n itself is a prime factor with exponent 1. - Building SPF with primes only but forgetting to fill composites: ensure the sieve correctly assigns spf for every number. - Ignoring performance needs: using trial division for many large queries can time out; choose SPF or Pollard’s Rho appropriately. - Not randomizing Pollard’s Rho polynomial or seed: fixed bad choices can cause cycles that fail to find a factor; retry with new constants or seeds.

Key Formulas

Fundamental Theorem of Arithmetic (factorized form)

Explanation: Every integer can be written uniquely as a product of prime powers. The primes are distinct and are positive integers.

Number of Divisors

Explanation: If n factors as \( p_\), then the count of divisors equals the product over (exponent + 1). Each exponent contributes choices from 0 to .

Sum of Divisors

Explanation: The sum over all divisors factors into geometric series for each prime power. Multiply those sums to get the total.

Euler’s Totient

Explanation: The count of integers coprime to n is n times the product over (1 - 1/p) for each distinct prime factor p. This follows from inclusion–exclusion.

Trial Division Complexity

Explanation: Checking divisibility up to \(\) bounds the number of trial factors. It grows with the square root of n, which is feasible for moderate n.

Sieve Preprocessing

Explanation: An SPF (or prime) sieve up to N runs in near-linear time. After that, each factorization of is very fast.

SPF Factorization Per Query

Explanation: Repeatedly dividing by the smallest prime factor reduces n quickly; the number of steps is proportional to the number of prime factors, which is at most O(log n).

Pollard’s Rho Expected Time

Explanation: Heuristically, Pollard’s Rho finds a nontrivial factor in time about the fourth root of n. This is fast enough for 64-bit inputs in practice.

Binary Exponentiation

Explanation: Write b in binary and square-and-multiply for bits . This reduces exponentiation to O(log b) modular multiplications.

Euclidean Algorithm

Explanation: The greatest common divisor can be found via repeated remainders. This runs in logarithmic time relative to the sizes of a and b.

Complexity Analysis

Trial division runs in O() time in the worst case because you only need to test factors up to the square root; you can halve the work by skipping even numbers and slightly more via wheels (e.g., mod 6 or mod 30). Space usage is O(1). This is ideal for single queries with n up to about 10^12 in optimized C++, though worst-case primes near the limit still cost \( \) iterations. An SPF sieve up to N precomputes an array of size N, taking O(N N) time and O(N) memory. After preprocessing, factorization of any takes O(log x) time because each step divides by at least the smallest prime factor, and the number of prime factors with multiplicity is bounded by O(log x). For many queries (e.g., ) with moderate N (≤ 10^7–10^8 depending on memory), SPF is highly efficient. For general 64-bit integers, Miller–Rabin primality testing runs in O(k log n) modular multiplications for k bases; with fixed deterministic bases for 64-bit, k is a small constant, so it is effectively O(log n). Pollard’s Rho finds nontrivial factors in expected O() time under heuristic assumptions; in practice, factoring up to 10^18 is routinely fast, especially when combined with trial division by small primes to strip easy factors. The recursive splitting continues until all prime factors are found. Space usage remains small: O(1) aside from recursion depth and a few variables, typically O(log n). Careful modular multiplication (using 128-bit intermediates) avoids overflow, keeping each modular operation O(1) on 64-bit hardware.

Code Examples

Single-number factorization by optimized trial division
1#include <bits/stdc++.h>
2using namespace std;
3
4// Factor n using trial division up to sqrt(n)
5// Returns vector of (prime, exponent)
6vector<pair<uint64_t,int>> factor_trial(uint64_t n){
7    vector<pair<uint64_t,int>> res;
8    if(n <= 1) return res;
9    int cnt = 0;
10    while((n & 1ull) == 0){ n >>= 1; cnt++; }
11    if(cnt) res.push_back({2, cnt});
12    for(uint64_t d = 3; d <= n / d; d += 2){
13        if(n % d == 0){
14            int e = 0;
15            do { n /= d; e++; } while(n % d == 0);
16            res.push_back({d, e});
17        }
18    }
19    if(n > 1) res.push_back({n, 1});
20    return res;
21}
22
23int main(){
24    ios::sync_with_stdio(false);
25    cin.tie(nullptr);
26
27    uint64_t n; 
28    if(!(cin >> n)) return 0;
29    auto f = factor_trial(n);
30    // Print n = p1^e1 * p2^e2 * ...
31    if(f.empty()){ cout << n << " has no prime factorization (n <= 1)\n"; return 0; }
32    cout << n << " = ";
33    for(size_t i = 0; i < f.size(); ++i){
34        cout << f[i].first;
35        if(f[i].second > 1) cout << "^" << f[i].second;
36        if(i + 1 < f.size()) cout << " * ";
37    }
38    cout << "\n";
39    return 0;
40}
41

This program factors a single 64-bit integer using trial division. It first removes all factors of 2, then checks odd divisors up to sqrt(n). Any leftover n > 1 is prime. It prints the factorization in prime-power form.

Time: O(\sqrt{n}) in the worst case (n prime), with a factor-of-two improvement by skipping evens.Space: O(1) extra space aside from output.
Many queries with SPF sieve (fast \u201cO(log n)\u201d factorization)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Build SPF (smallest prime factor) for all numbers up to MAXN
5vector<int> build_spf(int MAXN){
6    vector<int> spf(MAXN + 1);
7    for(int i = 0; i <= MAXN; ++i) spf[i] = i; // initialize
8    for(int i = 2; i * 1ll * i <= MAXN; ++i){
9        if(spf[i] == i){ // i is prime
10            for(long long j = 1ll * i * i; j <= MAXN; j += i){
11                if(spf[(int)j] == j) spf[(int)j] = i;
12            }
13        }
14    }
15    // For primes > sqrt(MAXN), spf[p] stays p; composites already updated.
16    return spf;
17}
18
19vector<pair<int,int>> factor_spf(int x, const vector<int>& spf){
20    vector<pair<int,int>> res;
21    while(x > 1){
22        int p = spf[x];
23        int e = 0;
24        while(x % p == 0){ x /= p; ++e; }
25        res.push_back({p, e});
26    }
27    return res;
28}
29
30int main(){
31    ios::sync_with_stdio(false);
32    cin.tie(nullptr);
33
34    int Q, MAXN; 
35    cin >> Q >> MAXN; // read number of queries and max value
36    vector<int> spf = build_spf(MAXN);
37    while(Q--){
38        int x; cin >> x;
39        auto f = factor_spf(x, spf);
40        cout << x << " = ";
41        for(size_t i = 0; i < f.size(); ++i){
42            cout << f[i].first;
43            if(f[i].second > 1) cout << "^" << f[i].second;
44            if(i + 1 < f.size()) cout << " * ";
45        }
46        cout << "\n";
47    }
48    return 0;
49}
50

Precompute spf[x] for all x ≤ MAXN in O(MAXN log log MAXN). Then each query factors x by repeatedly dividing by its smallest prime, yielding O(log x) time per factorization. This is excellent for many queries over a bounded range.

Time: Preprocessing O(N log log N); each factorization O(log n).Space: O(N) for the spf array.
64-bit factorization with Miller\u2013Rabin and Pollard\u2019s Rho
1#include <bits/stdc++.h>
2using namespace std;
3using u64 = uint64_t; 
4using u128 = __uint128_t;
5
6u64 mod_mul(u64 a, u64 b, u64 mod){
7    return (u128)a * b % mod; // safe using 128-bit
8}
9
10u64 mod_pow(u64 a, u64 e, u64 mod){
11    u64 r = 1;
12    while(e){
13        if(e & 1) r = mod_mul(r, a, mod);
14        a = mod_mul(a, a, mod);
15        e >>= 1;
16    }
17    return r;
18}
19
20bool is_prime(u64 n){
21    if(n < 2) return false;
22    for(u64 p : {2ull,3ull,5ull,7ull,11ull,13ull,17ull}){
23        if(n % p == 0) return n == p;
24    }
25    u64 d = n - 1, s = 0;
26    while((d & 1) == 0){ d >>= 1; ++s; }
27    auto check = [&](u64 a){
28        if(a % n == 0) return true;
29        u64 x = mod_pow(a, d, n);
30        if(x == 1 || x == n - 1) return true;
31        for(u64 r = 1; r < s; ++r){
32            x = mod_mul(x, x, n);
33            if(x == n - 1) return true;
34        }
35        return false;
36    };
37    // Deterministic for 64-bit with these bases
38    for(u64 a : {2ull,325ull,9375ull,28178ull,450775ull,9780504ull,1795265022ull}){
39        if(!check(a)) return false;
40    }
41    return true;
42}
43
44u64 rng_u64(){
45    static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
46    return rng();
47}
48
49u64 pollard_rho(u64 n){
50    if((n & 1ull) == 0) return 2;
51    if(n % 3ull == 0) return 3;
52    u64 c = (rng_u64() % (n - 1)) + 1; // 1..n-1
53    u64 x = (rng_u64() % (n - 2)) + 2; // 2..n-1
54    u64 y = x;
55    u64 d = 1;
56    auto f = [&](u64 v){ return (mod_mul(v, v, n) + c) % n; };
57    while(d == 1){
58        x = f(x);
59        y = f(f(y));
60        u64 diff = x > y ? x - y : y - x;
61        d = std::gcd(diff, n);
62        if(d == n) return pollard_rho(n); // retry with new parameters
63    }
64    return d;
65}
66
67void factor(u64 n, map<u64,int>& fac){
68    if(n == 1) return;
69    if(is_prime(n)){ fac[n]++; return; }
70    u64 d = pollard_rho(n);
71    factor(d, fac);
72    factor(n / d, fac);
73}
74
75int main(){
76    ios::sync_with_stdio(false);
77    cin.tie(nullptr);
78
79    int Q; cin >> Q;
80    while(Q--){
81        u64 n; cin >> n;
82        if(n <= 1){ cout << n << " has no prime factorization (n <= 1)\n"; continue; }
83        map<u64,int> fac;
84        // Optional: strip small primes quickly
85        for(u64 p : {2ull,3ull,5ull,7ull,11ull,13ull,17ull,19ull,23ull,29ull,31ull,37ull}){
86            while(n % p == 0){ fac[p]++; n /= p; }
87        }
88        if(n > 1) factor(n, fac);
89        cout << "Factors:";
90        bool first = true;
91        for(auto &kv : fac){
92            cout << (first ? " " : " * ") << kv.first;
93            if(kv.second > 1) cout << "^" << kv.second;
94            first = false;
95        }
96        cout << "\n";
97    }
98    return 0;
99}
100

This template factors arbitrary 64-bit integers. It uses a deterministic Miller–Rabin variant for primality, safe 128-bit modular arithmetic, and Pollard’s Rho to split composites recursively. Small primes are stripped first to accelerate typical cases.

Time: Expected O(n^{1/4}) per hard composite due to Pollard’s Rho, with very fast behavior in practice; Miller–Rabin is O(log n) modular operations.Space: O(log n) due to recursion depth; otherwise O(1) auxiliary.
From factorization to divisor functions (τ, σ, φ)
1#include <bits/stdc++.h>
2using namespace std;
3using u64 = uint64_t; using u128 = __uint128_t;
4
5u64 mod_mul(u64 a, u64 b, u64 mod){ return (u128)a * b % mod; }
6u64 mod_pow(u64 a, u64 e, u64 mod){ u64 r=1; while(e){ if(e&1) r=mod_mul(r,a,mod); a=mod_mul(a,a,mod); e>>=1;} return r; }
7
8// Simple trial division for demo (replace with SPF or Rho as needed)
9vector<pair<u64,int>> factor_trial(u64 n){
10    vector<pair<u64,int>> f; if(n<=1) return f; int c=0; while((n&1ull)==0){n>>=1; c++;} if(c) f.push_back({2,c});
11    for(u64 d=3; d<=n/d; d+=2){ if(n%d==0){int e=0; do{n/=d; e++;}while(n%d==0); f.push_back({d,e}); } }
12    if(n>1) f.push_back({n,1}); return f;
13}
14
15// τ(n) = product (e_i + 1)
16unsigned long long tau_from_factors(const vector<pair<u64,int>>& f){
17    unsigned long long res = 1;
18    for(auto &pe: f) res *= (unsigned long long)(pe.second + 1);
19    return res;
20}
21
22// σ(n) = product (p^{e+1}-1)/(p-1)
23unsigned long long sigma_from_factors(const vector<pair<u64,int>>& f){
24    unsigned long long res = 1;
25    for(auto &pe: f){
26        u64 p = pe.first; int e = pe.second;
27        // Compute geometric sum safely in 128-bit then cast (may overflow if huge)
28        __uint128_t num = 1; // p^{e+1} - 1
29        for(int i=0;i<e+1;i++) num *= p;
30        num -= 1;
31        unsigned long long term = (unsigned long long)(num / (p - 1));
32        res = res * term; // beware: can overflow 64-bit for very large n
33    }
34    return res;
35}
36
37// φ(n) = n * product (1 - 1/p)
38unsigned long long phi_from_factors(u64 n, const vector<pair<u64,int>>& f){
39    __uint128_t r = n;
40    for(auto &pe: f){ r = r / pe.first * (pe.first - 1); }
41    return (unsigned long long)r; // fits if n fits and not too large result
42}
43
44int main(){
45    ios::sync_with_stdio(false); cin.tie(nullptr);
46    u64 n; if(!(cin >> n)) return 0;
47    auto f = factor_trial(n);
48    cout << n << " = ";
49    for(size_t i=0;i<f.size();++i){ cout << f[i].first; if(f[i].second>1) cout << "^"<<f[i].second; if(i+1<f.size()) cout<<" * "; }
50    cout << "\n";
51    cout << "tau(n) = " << tau_from_factors(f) << "\n";
52    cout << "phi(n) = " << phi_from_factors(n, f) << "\n";
53    cout << "sigma(n) = " << sigma_from_factors(f) << "\n";
54    return 0;
55}
56

Given the prime-power factorization of n, compute the number of divisors τ(n), Euler’s totient φ(n), and the sum of divisors σ(n) using their multiplicative formulas. Trial division is used here for simplicity; in production, plug in SPF or Rho.

Time: Factorization dominates: O(\sqrt{n}) here; postprocessing is O(k) where k is the number of distinct primes.Space: O(1) extra aside from storing factors.