Smallest Prime Factors
For each , let be its smallest prime factor. For a prime , this gives .
Build the table once through the largest query value. Each later factorization can use the stored factors directly instead of searching for divisors.
Initially, all entries are zero. Process candidates in increasing order.
If is already set, is composite. Otherwise, is prime: set , then visit its multiples starting at . Write only into entries that are still zero.
Since primes are processed in increasing order, the first prime to write an entry is its smallest prime factor. Every composite is reached: its smallest prime factor satisfies .
As in Eratosthenes, smaller composite multiples of have already been marked. Primes larger than still receive their own entries, even though their marking loops are skipped.
For a remaining value , read . Divide by until it no longer divides , count the divisions, and record .
Repeat until . Each step removes one prime completely, so the resulting pairs are in increasing prime order. The factorization of is empty.
Building the table takes time and memory. Writing only unset entries preserves the smallest factor; the marking loops still visit previously set entries.
Each successful division reduces the query value by at least a factor of two. Thus factoring takes time. The query uses extra memory apart from the returned pairs.
#include <bits/stdc++.h>
using namespace std;
vector<int> spf;
void build(int n) {
spf.assign(n + 1, 0);
for (int p = 2; p <= n; p++) {
if (spf[p] != 0) {
continue;
}
spf[p] = p;
if (p > n / p) {
continue;
}
for (long long x = 1LL * p * p; x <= n; x += p) {
if (spf[(int)x] == 0) {
spf[(int)x] = p;
}
}
}
}
vector<pair<int, int>> factor(int x) {
vector<pair<int, int>> res;
while (x > 1) {
int p = spf[x], e = 0;
while (x % p == 0) {
x /= p;
e++;
}
res.push_back({p, e});
}
return res;
}