数学/prime sieve
(test/math/prime_sieve.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://yukicoder.me/problems/no/843

Depends on

• prime sieve (include/emthrm/math/prime_sieve.hpp)

Code

/*
 * @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;
}

Back to top page