Sieve of Eratosthenes
(Mylib/Number/Prime/sieve_eratosthenes.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

• https://qiita.com/peria/items/a4ff4ddb3336f7b81d50

Verified with

• test/yosupo-judge/enumerate_primes/main.eratosthenes.test.cpp

Code

#pragma once
#include <vector>

namespace haar_lib {
  class eratosthenes_sieve {
    std::vector<bool> is_prime_;

  public:
    eratosthenes_sieve() {}
    eratosthenes_sieve(int MAX) : is_prime_((MAX + 1) / 2, true) {
      is_prime_[0] = false;

      for (int i = 3; i * i <= MAX; i += 2) {
        if (not is_prime_[i / 2]) continue;

        for (int j = i * i; j <= MAX; j += 2 * i) {
          is_prime_[j / 2] = false;
        }
      }
    }

    bool operator()(int i) const {
      if (i == 2) return true;
      if (i % 2 == 0) return false;
      return is_prime_[i / 2];
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Number/Prime/sieve_eratosthenes.cpp"
#include <vector>

namespace haar_lib {
  class eratosthenes_sieve {
    std::vector<bool> is_prime_;

  public:
    eratosthenes_sieve() {}
    eratosthenes_sieve(int MAX) : is_prime_((MAX + 1) / 2, true) {
      is_prime_[0] = false;

      for (int i = 3; i * i <= MAX; i += 2) {
        if (not is_prime_[i / 2]) continue;

        for (int j = i * i; j <= MAX; j += 2 * i) {
          is_prime_[j / 2] = false;
        }
      }
    }

    bool operator()(int i) const {
      if (i == 2) return true;
      if (i % 2 == 0) return false;
      return is_prime_[i / 2];
    }
  };
}  // namespace haar_lib

Back to top page