test/math/Enumerate_Primes.test.cpp

• View this file on GitHub
• Last update: 2023-08-23 17:33:30+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

• Eratosthenes Sieve (math/eratosthenes_sieve.hpp)

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;
    ebi::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 <cstdint>

#include <vector>


/*
    reference: https://37zigen.com/sieve-eratosthenes/
*/

namespace ebi {

struct eratosthenes_sieve {
  private:
    using i64 = std::int_fast64_t;
    int n;
    std::vector<bool> table;

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

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

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

}  // namespace ebi
#line 6 "test/math/Enumerate_Primes.test.cpp"

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    ebi::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";
}

Back to top page