test/yosupo-judge/enumerate_primes/main.eratosthenes.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"
#include <iostream>
#include <vector>
#include "Mylib/IO/join.cpp"
#include "Mylib/Number/Prime/sieve_eratosthenes.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, A, B;
std::cin >> N >> A >> B;
const auto is_prime = hl::eratosthenes_sieve(N);
int pi = 0;
std::vector<int> ans;
for (int i = 2; i <= N; ++i) {
if (is_prime(i)) {
if ((pi - B) % A == 0) {
ans.push_back(i);
}
++pi;
}
}
std::cout << pi << " " << ans.size() << "\n"
<< hl::join(ans.begin(), ans.end()) << "\n";
return 0;
}
#line 1 "test/yosupo-judge/enumerate_primes/main.eratosthenes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"
#include <iostream>
#include <vector>
#line 3 "Mylib/IO/join.cpp"
#include <sstream>
#include <string>
namespace haar_lib {
template <typename Iter>
std::string join(Iter first, Iter last, std::string delim = " ") {
std::stringstream s;
for (auto it = first; it != last; ++it) {
if (it != first) s << delim;
s << *it;
}
return s.str();
}
} // namespace haar_lib
#line 3 "Mylib/Number/Prime/sieve_eratosthenes.cpp"
namespace haar_lib {
class eratosthenes_sieve {
std::vector<bool> is_prime_;
public:
eratosthenes_sieve() {}
eratosthenes_sieve(int MAX) : is_prime_((MAX + 1) / 2, true) {
is_prime_[0] = false;
for (int i = 3; i * i <= MAX; i += 2) {
if (not is_prime_[i / 2]) continue;
for (int j = i * i; j <= MAX; j += 2 * i) {
is_prime_[j / 2] = false;
}
}
}
bool operator()(int i) const {
if (i == 2) return true;
if (i % 2 == 0) return false;
return is_prime_[i / 2];
}
};
} // namespace haar_lib
#line 7 "test/yosupo-judge/enumerate_primes/main.eratosthenes.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, A, B;
std::cin >> N >> A >> B;
const auto is_prime = hl::eratosthenes_sieve(N);
int pi = 0;
std::vector<int> ans;
for (int i = 2; i <= N; ++i) {
if (is_prime(i)) {
if ((pi - B) % A == 0) {
ans.push_back(i);
}
++pi;
}
}
std::cout << pi << " " << ans.size() << "\n"
<< hl::join(ans.begin(), ans.end()) << "\n";
return 0;
}
Back to top page