C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @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; }