Sieve (Smallest Prime Factor)
O(n log log n)Sieve of Eratosthenes that records each number's smallest prime factor instead of just primality. Same cost, strictly more useful: primality is spf[x] == x, and any x factorizes in O(log x) by repeatedly dividing out spf[x].
// use it on
CSES: Counting Divisors ↗
Divisor counts for up to 2·10^5 numbers. Factor each one in O(log x) via spf and multiply (exponent + 1) over the factorization.
// the code
// spf[x] = smallest prime factor of x (spf[x] == x <=> x is prime)
vector<int> sieve(int N) {
vector<int> spf(N + 1);
iota(spf.begin(), spf.end(), 0);
for (int i = 2; (long long)i * i <= N; i++)
if (spf[i] == i) // prime
for (int j = i * i; j <= N; j += i)
if (spf[j] == j) spf[j] = i;
return spf;
}
// factorize x in O(log x):
// while (x > 1) { int p = spf[x]; while (x % p == 0) x /= p; ... }