eratosthenes sieve
(math/eratosthenes_sieve.hpp)

• View this file on GitHub
• Last update: 2023-05-17 22:41:14+09:00
• Include: #include "math/eratosthenes_sieve.hpp"

説明

エラトステネスの篩

コンストラクタ

eratosthenes_sieve(int n)

上限値を $n$ としてエラトステネスの篩を実行。

is_prime(int p)

bool is_prime(int p)

$p$ が素数であるか判定

prime_table(int m = -1)

std::vector<int> prime_table(int m = -1)

$m$ 以下の素数を格納した配列を返す。 $m = -1$ のときは $m = n$ として実行

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/math/enumerate_primes.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

#include "../template/template.hpp"

namespace lib {

using namespace std;

struct eratosthenes_sieve {
  private:
    int n;
    vector<bool> table;

  public:
    eratosthenes_sieve(int n) : n(n), table(vector<bool>(n + 1, true)) {
        table[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (!table[i]) continue;
            for (int j = i; i * j <= n; j++) {
                table[i * j] = false;
            }
        }
    }

    bool is_prime(int p) {
        return table[p];
    }

    vector<int> prime_table(int m = -1) {
        if (m < 0) m = n;
        std::vector<int> prime;
        rep(i, 2, m + 1) {
            if (table[i]) prime.emplace_back(i);
        }
        return prime;
    }
};

}  // namespace lib

#line 2 "math/eratosthenes_sieve.hpp"

#include <cassert>
#include <vector>

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 7 "math/eratosthenes_sieve.hpp"

namespace lib {

using namespace std;

struct eratosthenes_sieve {
  private:
    int n;
    vector<bool> table;

  public:
    eratosthenes_sieve(int n) : n(n), table(vector<bool>(n + 1, true)) {
        table[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (!table[i]) continue;
            for (int j = i; i * j <= n; j++) {
                table[i * j] = false;
            }
        }
    }

    bool is_prime(int p) {
        return table[p];
    }

    vector<int> prime_table(int m = -1) {
        if (m < 0) m = n;
        std::vector<int> prime;
        rep(i, 2, m + 1) {
            if (table[i]) prime.emplace_back(i);
        }
        return prime;
    }
};

}  // namespace lib

Back to top page