math/eratosthenes-sieve.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/eratosthenes-sieve.hpp"

Depends on

• math/base.hpp

Code

#pragma once

#include "./base.hpp"

#include <vector>

namespace matumoto {
  struct EratosthenesSieve {
    vector<bool> prime_table;

    EratosthenesSieve() {}
    EratosthenesSieve(int N): prime_table(N + 1, true) {
      prime_table[0] = prime_table[1] = false;
    }

    void build() {
      int n = prime_table.size();
      for (ll i = 2; i * i < n; i++) {
        if (!prime_table[i])
          continue;
        for (ll j = i * i; j < n; j += i) {
          prime_table[j] = false;
        }
      }
    }

    bool operator[](int k) {
      return prime_table[k];
    }
  };
} // namespace matumoto

#line 2 "math/eratosthenes-sieve.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 4 "math/eratosthenes-sieve.hpp"

#include <vector>

namespace matumoto {
  struct EratosthenesSieve {
    vector<bool> prime_table;

    EratosthenesSieve() {}
    EratosthenesSieve(int N): prime_table(N + 1, true) {
      prime_table[0] = prime_table[1] = false;
    }

    void build() {
      int n = prime_table.size();
      for (ll i = 2; i * i < n; i++) {
        if (!prime_table[i])
          continue;
        for (ll j = i * i; j < n; j += i) {
          prime_table[j] = false;
        }
      }
    }

    bool operator[](int k) {
      return prime_table[k];
    }
  };
} // namespace matumoto

Back to top page