C++ Library for Competitive Programming
/*
* @title 数学/prime sieve
*
* verification-helper: PROBLEM https://yukicoder.me/problems/no/843
*/
#include <iostream>
#include <set>
#include <vector>
#include "emthrm/math/prime_sieve.hpp"
int main() {
int n;
std::cin >> n;
const std::vector<int> tmp = emthrm::prime_sieve<true>(n);
const std::set<int> prime(tmp.begin(), tmp.end());
int ans = 0;
for (const int p : prime) {
if (p * p - 2 > n) break;
if (prime.contains(p * p - 2)) ans += (p == 2 ? 1 : 2);
}
std::cout << ans << '\n';
return 0;
}
#line 1 "test/math/prime_sieve.test.cpp"
/*
* @title 数学/prime sieve
*
* verification-helper: PROBLEM https://yukicoder.me/problems/no/843
*/
#include <iostream>
#include <set>
#include <vector>
#line 1 "include/emthrm/math/prime_sieve.hpp"
#include <numeric>
#line 6 "include/emthrm/math/prime_sieve.hpp"
namespace emthrm {
template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
std::vector<int> smallest_prime_factor(n + 1), prime;
std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
for (int i = 2; i <= n; ++i) {
if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
for (const int p : prime) {
if (i * p > n || p > smallest_prime_factor[i]) break;
smallest_prime_factor[i * p] = p;
}
}
return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}
} // namespace emthrm
#line 12 "test/math/prime_sieve.test.cpp"
int main() {
int n;
std::cin >> n;
const std::vector<int> tmp = emthrm::prime_sieve<true>(n);
const std::set<int> prime(tmp.begin(), tmp.end());
int ans = 0;
for (const int p : prime) {
if (p * p - 2 > n) break;
if (prime.contains(p * p - 2)) ans += (p == 2 ? 1 : 2);
}
std::cout << ans << '\n';
return 0;
}