number-theory/test/Enumerate_Primes.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

• Sieve of Eratosthenes (using bitset) (number-theory/bitset_sieve.hpp)

Code

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

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;

#include "number-theory/bitset_sieve.hpp"

void solve(int ith) {
  int n, a, b;
  cin >> n >> a >> b;
  bitset_sieve<int(5e8 + 1)> sieve(n);
  vector<int> ans;
  for (int i = 0; a * i + b < (int)sieve.primes.size(); ++i)
    ans.push_back(sieve.primes[a * i + b]);
  cout << sieve.primes.size() << ' ' << ans.size() << '\n';
  for (auto v : ans) cout << v << ' ';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) solve(i);
}

#line 1 "number-theory/test/Enumerate_Primes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;

#line 1 "number-theory/bitset_sieve.hpp"
template <int LIMN>
struct bitset_sieve {
  vector<int> primes;
  bitset<LIMN + 1> is_prime;
  const int maxN;
  bitset_sieve(int MAXN = LIMN) : maxN(MAXN) {
    is_prime.set();
    is_prime.reset(0), is_prime.reset(1);
    for (int p = 2; p <= MAXN; p++) {
      if (is_prime[p]) {
        primes.push_back(p);
        for (int j = p * 2; j <= MAXN; j += p) is_prime[j] = 0;
      }
    }
  }
  // Count primes less than or equal to x
  int prime_counting(int x) {
    assert(x <= maxN);
    return distance(primes.begin(),
                    upper_bound(primes.begin(), primes.end(), x));
  }
};
#line 12 "number-theory/test/Enumerate_Primes.test.cpp"

void solve(int ith) {
  int n, a, b;
  cin >> n >> a >> b;
  bitset_sieve<int(5e8 + 1)> sieve(n);
  vector<int> ans;
  for (int i = 0; a * i + b < (int)sieve.primes.size(); ++i)
    ans.push_back(sieve.primes[a * i + b]);
  cout << sieve.primes.size() << ' ' << ans.size() << '\n';
  for (auto v : ans) cout << v << ' ';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) solve(i);
}

Back to top page