test/math/enumerate_primes.test.cpp

View this file on GitHub
Last update: 2023-05-17 22:41:14+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

Code

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

#include <iostream>

#include "../../math/eratosthenes_sieve.hpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    lib::eratosthenes_sieve sieve(n);
    auto p = sieve.prime_table();
    int sz = p.size();
    int x = (sz - b + a - 1) / a;
    std::cout << sz << " " << x << '\n';
    for (int i = b; i < sz; i += a) {
        std::cout << p[i] << " ";
    }
    std::cout << "\n";
}

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

#include <iostream>

#line 2 "math/eratosthenes_sieve.hpp"

#include <cassert>
#include <vector>

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 7 "math/eratosthenes_sieve.hpp"

namespace lib {

using namespace std;

struct eratosthenes_sieve {
  private:
    int n;
    vector<bool> table;

  public:
    eratosthenes_sieve(int n) : n(n), table(vector<bool>(n + 1, true)) {
        table[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (!table[i]) continue;
            for (int j = i; i * j <= n; j++) {
                table[i * j] = false;
            }
        }
    }

    bool is_prime(int p) {
        return table[p];
    }

    vector<int> prime_table(int m = -1) {
        if (m < 0) m = n;
        std::vector<int> prime;
        rep(i, 2, m + 1) {
            if (table[i]) prime.emplace_back(i);
        }
        return prime;
    }
};

}  // namespace lib
#line 6 "test/math/enumerate_primes.test.cpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    lib::eratosthenes_sieve sieve(n);
    auto p = sieve.prime_table();
    int sz = p.size();
    int x = (sz - b + a - 1) / a;
    std::cout << sz << " " << x << '\n';
    for (int i = b; i < sz; i += a) {
        std::cout << p[i] << " ";
    }
    std::cout << "\n";
}