This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#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); }