Skip to content

Primes & Factors

Primes are integers \(> 1\) with no positive divisors other than \(1\) and themselves. Factorization expresses \(n\) as a product of primes.

Trial division

vector<long long> trialFactor(long long n) {
    vector<long long> f;
    for (long long d = 2; d * d <= n; d++)
        while (n % d == 0) {
            f.push_back(d);
            n /= d;
        }
    if (n > 1) f.push_back(n);
    return f;
}

Smallest prime factor (SPF) sieve

For all \(n \le N\), precompute spf[n] in \(O(N \log\log N)\), then factor \(n\) in \(O(\log n)\) by dividing out spf repeatedly.

vector<int> buildSpf(int N) {
    vector<int> spf(N + 1);
    for (int i = 0; i <= N; i++) spf[i] = i;
    for (int i = 2; i * i <= N; i++)
        if (spf[i] == i)
            for (int j = i * i; j <= N; j += i)
                if (spf[j] == j) spf[j] = i;
    return spf;
}

Uses

  • GCD/LCM from prime exponents: \(\text{lcm}(a,b) = \prod p^{\max(\alpha,\beta)}\).
  • Euler totient \(\varphi(n)\) from factorization.
  • Divisors count / sum from exponent formula.