verify/lc_math/lc_enumerate_primes.test.cpp

View this file on GitHub
Last update: 2023-02-06 17:52:27+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"

#include <bits/stdc++.h>

#include "math/enumerate_primes.hpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    auto pl = enumerate_primes(n);
    std::vector<int> ans;
    for (int i = b; i < pl.size(); i += a) ans.push_back(pl[i]);
    std::cout << pl.size() << ' ' << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) std::cout << ans[i] << " \n"[i == ans.size() - 1];
    return 0;
}

#line 1 "verify/lc_math/lc_enumerate_primes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"

#include <bits/stdc++.h>

#line 2 "math/enumerate_primes.hpp"

#line 2 "math/prime_table.hpp"

std::vector<bool> prime_table(int n) {
    std::vector<bool> res(n + 1, true);
    if (n >= 0) res[0] = false;
    if (n >= 1) res[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (!res[p]) continue;
        for (int i = p * p; i <= n; i += p) {
            res[i] = false;
        }
    }
    return res;
}
#line 4 "math/enumerate_primes.hpp"

std::vector<int> enumerate_primes(int n) {
    auto pt = prime_table(n);
    std::vector<int> res;
    res.reserve(std::count(pt.begin(), pt.end(), true));
    for (int i = 0; i < pt.size(); i++) {
        if (pt[i]) res.push_back(i);
    }
    return res;
}
#line 6 "verify/lc_math/lc_enumerate_primes.test.cpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    auto pl = enumerate_primes(n);
    std::vector<int> ans;
    for (int i = b; i < pl.size(); i += a) ans.push_back(pl[i]);
    std::cout << pl.size() << ' ' << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) std::cout << ans[i] << " \n"[i == ans.size() - 1];
    return 0;
}