エラトステネスの篩
(math/eratosthenes.hpp)

• View this file on GitHub
• Last update: 2023-02-25 23:57:16+09:00
• Include: #include "math/eratosthenes.hpp"

Verified with

• test/aoj/aoj-ALDS1-1-C_2.test.cpp
• test/aoj/aoj2858.test.cpp

Code

#pragma once

#include <vector>

class Eratosthenes {
  public:
    Eratosthenes() {}
    explicit Eratosthenes(int n) : n(n), isp(n + 1, true) {
        isp[0] = isp[1] = false;
        for(int i = 2; i * i <= n; i++) {
            if(!isp[i]) continue;
            for(int j = i * i; j <= n; j += i) isp[j] = false;
        }
    }
    bool operator[](int k) const { return isp[k]; }

  private:
    int n;
    std::vector<bool> isp;
};

#line 2 "math/eratosthenes.hpp"

#include <vector>

class Eratosthenes {
  public:
    Eratosthenes() {}
    explicit Eratosthenes(int n) : n(n), isp(n + 1, true) {
        isp[0] = isp[1] = false;
        for(int i = 2; i * i <= n; i++) {
            if(!isp[i]) continue;
            for(int j = i * i; j <= n; j += i) isp[j] = false;
        }
    }
    bool operator[](int k) const { return isp[k]; }

  private:
    int n;
    std::vector<bool> isp;
};

Back to top page