uniolympiads Ελληνικά

Linear sieve

The primes up to nn and the smallest prime factor of every number in O(n)O(n). Then factorisation in O(log⁡x)O(\log x).

When

Many numbers up to 10610^6 or 10710^7 that must be factorised, or a function such as the number of divisors or φ\varphi for all numbers up to nn.

The idea

Every composite xx is written uniquely as x=p⋅ix = p \cdot i, where pp is the smallest prime factor of xx. Then p≤spf(i)p \le \mathrm{spf}(i). For each ii, go through the primes p≤spf(i)p \le \mathrm{spf}(i) and set spf(p⋅i)=p\mathrm{spf}(p \cdot i) = p. Every composite is marked exactly once, so O(n)O(n).

The sieve of Eratosthenes is O(nlog⁡log⁡n)O(n \log \log n) and almost as fast. The linear one is worth it because it gives the spf\mathrm{spf} table for free. With it, factorising xx is "divide by spf(x)\mathrm{spf}(x) until you reach 1", at most log⁡2x\log_2 x steps.

Number of divisors

If x=p1e1⋯pkekx = p_1^{e_1} \cdots p_k^{e_k}, the number of divisors is (e1+1)⋯(ek+1)(e_1 + 1) \cdots (e_k + 1). In Counting Divisors (10510^5 numbers up to 10610^6) this is one factorize per number.

Pitfalls

  • The spf\mathrm{spf} table for n=107n = 10^7 is 40 MB as int. For 10610^6 it is negligible.
  • The check (ll)p * i > n is done in long long: for nn near 2312^{31} the product overflows in int.
  • The test compares every number up to 10510^5 against trial division, and checks that π(105)=9592\pi(10^5) = 9592.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/sieve.cpp
// 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.

More in the USACO Guide

In English, with more problems per level.