数学/segmented sieve
(test/math/segmented_sieve.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bt

Depends on

• segmented sieve (include/emthrm/math/segmented_sieve.hpp)

Code

/*
 * @title 数学/segmented sieve
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bt
 */

#include <algorithm>
#include <iostream>

#include "emthrm/math/segmented_sieve.hpp"

int main() {
  long long l, r;
  std::cin >> l >> r;
  std::cout << std::ranges::count(emthrm::segmented_sieve(l, r + 1), true)
            << '\n';
  return 0;
}

#line 1 "test/math/segmented_sieve.test.cpp"
/*
 * @title 数学/segmented sieve
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bt
 */

#include <algorithm>
#include <iostream>

#line 1 "include/emthrm/math/segmented_sieve.hpp"



#line 5 "include/emthrm/math/segmented_sieve.hpp"
#include <cmath>
#include <iterator>
#include <vector>

namespace emthrm {

std::vector<bool> segmented_sieve(const long long low, const long long high) {
  long long root = 1;
  while ((root + 1) * (root + 1) < high) ++root;
  std::vector<bool> is_prime(root + 1, true);
  is_prime[0] = false;
  is_prime[1] = false;
  std::vector<bool> res(high - low, true);
  if (low < 2) std::fill(res.begin(), std::next(res.begin(), 2 - low), false);
  for (long long i = 2; i <= root; ++i) {
    if (is_prime[i]) [[unlikely]] {
      for (long long j = i * i; j <= root; j += i) {
        is_prime[j] = false;
      }
      for (long long j = std::max((low + i - 1) / i, 2LL) * i; j < high;
           j += i) {
        res[j - low] = false;
      }
    }
  }
  return res;
}

}  // namespace emthrm


#line 12 "test/math/segmented_sieve.test.cpp"

int main() {
  long long l, r;
  std::cin >> l >> r;
  std::cout << std::ranges::count(emthrm::segmented_sieve(l, r + 1), true)
            << '\n';
  return 0;
}

Back to top page