Sieve + Prime Factors

Sieve Prime Factors — SPF + Fast Factorization

[Number Theory]|

Aug 14, 2026

|explanatory_notes.md|

#Sieve#Prime-Factors

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> SPF;
vector<vector<int>> primeFactors;

vector<int> prime_factors(int x) {
  vector<int> ret;
  while (x > 1) {
    ret.push_back(SPF[x]);
    x /= SPF[x];
  }
  return ret;
}

void build_spf(int N) {
  SPF = vector<int>(N + 5);
  primeFactors = vector<vector<int>>(N + 5);

  for (int i = 1; i <= N; i++) {
    SPF[i] = i;
  }

  for (int i = 2; i <= N; i += 2) {
    SPF[i] = 2;
  }

  for (int i = 3; i * i <= N; i++) {
    if (SPF[i] == i) {
      for (int j = i * i; j <= N; j += i) {
        if (SPF[j] == j) {
          SPF[j] = i;
        }
      }
    }
  }

  for (int i = 1; i <= N; i++) {
    primeFactors[i] = prime_factors(i);
  }
}

void Solve() {
  // write your code here
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) Solve();
  return 0;
}

55 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Sieve Prime Factors — SPF + Fast Factorization

Quick Start (ECPC)

void Solve()
{
    int n; cin >> n;
    build_spf(n);    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        auto pf = prime_factors(x);  // {2, 2, 2, 3, 3, 5} for 360
        for (auto p : pf) cout << p << " ";
        cout << "\n";
    }
}

Functions

build_spf(N) — build SPF[] and primeFactors[] for 1..N

prime_factors(x) — returns vector, prime factors of x

Globals

SPF[i] — smallest prime factor of i

primeFactors[i] — precomputed prime factors of i

Notes

Call build_spf(N) once at the start.

prime_factors(x) runs in O(log x) using SPF.

Use for: factorization, divisor enumeration, GCD/LCM problems.

N up to 1e6-1e7 is fine.