Linear sieve
The primes up to and the smallest prime factor of every number in . Then factorisation in .
When
Many numbers up to or that must be factorised, or a function such as the number of divisors or for all numbers up to .
The idea
Every composite is written uniquely as , where is the smallest prime factor of . Then . For each , go through the primes and set . Every composite is marked exactly once, so .
The sieve of Eratosthenes is and almost as fast. The linear one is worth it because it gives the table for free. With it, factorising is "divide by until you reach 1", at most steps.
Number of divisors
If , the number of divisors is . In Counting Divisors ( numbers up to ) this is one factorize per number.
Pitfalls
- The table for is 40 MB as
int. For it is negligible. - The check
(ll)p * i > nis done inlong long: for near the product overflows inint. - The test compares every number up to against trial division, and checks that .
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Linear sieve: primes up to n and the smallest prime factor of every number. O(n).
// Every composite x is crossed out exactly once, by its smallest prime factor.
// factorize(x) then runs in O(log x) for x <= n.
struct Sieve {
vector<int> spf;
vector<int> primes;
Sieve(int n) : spf(n + 1, 0) {
for (int i = 2; i <= n; i++) {
if (spf[i] == 0) {
spf[i] = i;
primes.push_back(i);
}
for (int p : primes) {
if (p > spf[i] || (ll)p * i > n) {
break;
}
spf[p * i] = p;
}
}
}
bool isPrime(int x) {
return x >= 2 && spf[x] == x;
}
// (prime, exponent) pairs in increasing order of the prime.
vector<pair<int, int>> factorize(int x) {
vector<pair<int, int>> f;
while (x > 1) {
int p = spf[x];
int e = 0;
while (x % p == 0) {
x /= p;
e++;
}
f.push_back({p, e});
}
return f;
}
};
Tested on 100,001 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Counting Divisors · Mathematics
- Common Divisors · Mathematics
More in the USACO Guide
- Divisibility · usaco.guide/gold/divisibility
In English, with more problems per level.