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

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/segmented_sieve.hpp"

時間計算量

$O\left(\sqrt{H}\log{\log{H}} + \frac{(H - L)\sqrt{H}}{\log{H}}\right)$ ?

仕様

名前	戻り値
std::vector<bool> segmented_sieve(const long long low, const long long high);	$i$ ($\mathrm{low} \leq i < \mathrm{high}$) が素数であるか。

参考文献

• http://www.prefield.com/algorithm/math/segment_sieve.html

TODO

• https://uwitenpen.hatenadiary.org/entries/2011/12/03

Submissons

https://atcoder.jp/contests/math-and-algorithm/submissions/29613055

Verified with

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

Code

#ifndef EMTHRM_MATH_SEGMENTED_SIEVE_HPP_
#define EMTHRM_MATH_SEGMENTED_SIEVE_HPP_

#include <algorithm>
#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

#endif  // EMTHRM_MATH_SEGMENTED_SIEVE_HPP_

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



#include <algorithm>
#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

Back to top page