Prime Factorization
Break numbers into prime powers and choose the right factorization strategy for the size and query pattern.
Prime Factorization
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Prime factorization is the step that exposes arithmetic structure. Once a number is written as a product of prime powers, questions about divisors, gcd/lcm, multiplicative functions, and modular conditions usually become much clearer.
When to Use It
Use factorization when:
divisor counts or divisor sums matter,
the statement talks about prime powers or coprimality,
a multiplicative function needs to be evaluated from the prime exponents,
the input size suggests the factors themselves are more useful than the raw number.
Core Idea
Every positive integer has a unique factorization: \[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}. \] The implementation question is not whether this decomposition exists, but which method finds it fast enough:
trial division,
sieve-assisted factorization,
Pollard Rho for harder 64-bit cases.
Key Insight
Factorization is usually the preprocessing, not the end goal. The real value is what it unlocks afterward: divisor enumeration, phi, Mobius, CRT conditions, and multiplicative formulas.
Operations / Main Technique
divide by each prime factor while it still fits,
count the exponent of each factor,
if the remaining value is \(> 1\), it is prime in the trial-division setting.
Worked example.
If \(n = 360\), then \[ 360 = 2^3 \cdot 3^2 \cdot 5. \] From that, the divisor count is \((3+1)(2+1)(1+1) = 24\).
Correctness Intuition
Whenever a prime \(p\) divides \(n\), dividing out all copies of \(p\) records its exponent exactly. After all primes up to \(\sqrt{n}\) are tested, any remaining value must itself be prime, because a composite remainder would still have a factor at most its square root.
Complexity Analysis
trial division: \(O(\sqrt{n})\),
repeated queries with smallest-prime-factor sieve: roughly \(O(\log n)\) per number after preprocessing,
large 64-bit inputs may need Miller-Rabin plus Pollard Rho.
Implementation
The code includes:
basic trial-division factorization,
divisor generation from the prime-exponent list.
That is enough for many problems before the harder randomized methods become necessary.
Common Pitfalls
Trial-dividing up to the original \(\sqrt{n}\) instead of the shrinking current value.
Forgetting the leftover prime factor when the loop ends.
Building divisor formulas from distinct primes but ignoring their exponents.
Variants / Extensions
SPF sieve for many small-to-medium queries.
Pollard Rho for difficult 64-bit factorization.
Use factorization as the base for phi, Mobius, divisor sums, and multiplicative functions.
Practice Problems
Count divisors or sum divisors.
Factor many input values after one sieve.
Construct all divisors from the prime powers.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<pair<long long, int>> factorize_trial(long long n) {
vector<pair<long long, int>> factors;
for (long long p = 2; p * p <= n; ++p) {
if (n % p != 0) continue;
int exp = 0;
while (n % p == 0) {
n /= p;
++exp;
}
factors.push_back({p, exp});
}
if (n > 1) {
factors.push_back({n, 1});
}
return factors;
}
void generate_divisors_dfs(int idx, long long cur,
const vector<pair<long long, int>>& factors,
vector<long long>& divisors) {
if (idx == (int)factors.size()) {
divisors.push_back(cur);
return;
}
auto [p, exp] = factors[idx];
long long value = 1;
for (int e = 0; e <= exp; ++e) {
generate_divisors_dfs(idx + 1, cur * value, factors, divisors);
value *= p;
}
}
vector<long long> generate_divisors(const vector<pair<long long, int>>& factors) {
vector<long long> divisors;
generate_divisors_dfs(0, 1, factors, divisors);
sort(divisors.begin(), divisors.end());
return divisors;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.