test/library-checker/enumerate_primes.test.cpp

• View this file on GitHub
• Last update: 2026-10-26 01:59:35+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

• Sieve (math/sieve.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"
#include <iostream>
#include <vector>

#include "math/sieve.hpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    sieve s(n);
    const std::vector<int>& p = s.primes();
    std::vector<int> ans;
    for (int i = b; i < int(p.size()); i += a) ans.push_back(p[i]);
    std::cout << p.size() << ' ' << ans.size() << '\n';
    for (size_t i = 0; i < ans.size(); i++) std::cout << ans[i] << " \n"[i + 1 == ans.size()];
    if (ans.empty()) std::cout << '\n';
}

#line 1 "test/library-checker/enumerate_primes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"
#include <iostream>
#include <vector>

#line 2 "math/sieve.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#line 6 "math/sieve.hpp"
struct sieve {
public:
    sieve() : sieve(1) {
    }
    explicit sieve(int n) : _n(n), lpf(n + 1, 0) {
        assert(n >= 1);
        for (int i = 2; i <= n; i++) {
            if (lpf[i] == 0) {
                lpf[i] = i;
                _primes.push_back(i);
            }
            for (int p : _primes) {
                if (p > lpf[i] || (long long)p * i > n) break;
                lpf[p * i] = p;
            }
        }
    }
    bool is_prime(int x) const {
        assert(0 <= x && x <= _n);
        return x >= 2 && lpf[x] == x;
    }
    int smallest_prime_factor(int x) const {
        assert(2 <= x && x <= _n);
        return lpf[x];
    }
    const std::vector<int>& primes() const {
        return _primes;
    }
    std::vector<std::pair<int, int>> factorize(int x) const {
        assert(1 <= x && x <= _n);
        std::vector<std::pair<int, int>> ret;
        while (x > 1) {
            int p = lpf[x];
            if (!ret.empty() && ret.back().first == p) {
                ret.back().second++;
            } else {
                ret.emplace_back(p, 1);
            }
            x /= p;
        }
        return ret;
    }
    std::vector<int> divisors(int x) const {
        assert(1 <= x && x <= _n);
        std::vector<int> ret = {1};
        for (auto [p, e] : factorize(x)) {
            int sz = int(ret.size());
            int q = 1;
            for (int i = 0; i < e; i++) {
                q *= p;
                for (int j = 0; j < sz; j++) ret.push_back(ret[j] * q);
            }
        }
        std::sort(ret.begin(), ret.end());
        return ret;
    }

private:
    int _n;
    std::vector<int> lpf, _primes;
};
#line 6 "test/library-checker/enumerate_primes.test.cpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    sieve s(n);
    const std::vector<int>& p = s.primes();
    std::vector<int> ans;
    for (int i = b; i < int(p.size()); i += a) ans.push_back(p[i]);
    std::cout << p.size() << ' ' << ans.size() << '\n';
    for (size_t i = 0; i < ans.size(); i++) std::cout << ans[i] << " \n"[i + 1 == ans.size()];
    if (ans.empty()) std::cout << '\n';
}

Back to top page