质数筛

struct Sieve {
    int n;
    std::vector<int> f, primes;
    Sieve(int n = 1): n(n), f(n + 1) {
        f[0] = f[1] = -1;
        for (long long i = 2; i <= n; ++i) {
            if (f[i]) continue;
            primes.push_back(i);
            f[i] = i;
            for (long long j = i * i; j <= n; j += i) {
                if (!f[j]) f[j] = i;
            }
        }
    }
    bool is_prime(int x) {
        return f[x] == x;
    }
    std::vector<int> factorList(int x) {
        std::vector<int> res;
        while (x != 1) {
            res.push_back(f[x]);
            x /= f[x];
        }
        return res;
    }
    using pii = std::pair<int, int>;
    std::vector<pii> factor(int x) {
        std::vector<int> fl = factorList(x);
        if (fl.size() == 0) return {};
        std::vector<pii> res(1, pii(fl[0], 0));
        for (int p: fl) {
            if (res.back().first == p) ++res.back().second;
            else res.emplace_back(p, 1);
        }
        return res;
    }
    using pli = std::pair<long long, int>;
    std::vector<pli> factor(long long x) {
        std::vector<pli> res;
        for (int p: primes) {
            int y = 0;
            while (x % p == 0) {
                ++y;
                x /= p;
            }
            if (y) res.emplace_back(p, y);
        }
        if (x > 1) res.emplace_back(x, 1);
        return res;
    }
};