cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: エラトステネスの篩
(Src/Number/EratosthenesSieve.hpp)

概要

指定された正整数 $S$ 以下の全ての非負整数が、素数であるか素数でないかを判定し、結果を配列で保持します。

例えば、 $S = 5$ ならば、 $\{\ \text{false}, \text{false}, \text{true}, \text{true}, \text{false}, \text{true}\ \}$ です。

ライブラリの説明

コンストラクタ

(1) EratosthenesSieve()
(2) EratosthenesSieve(usize tableSize)

(1) デフォルトコンストラクタ
(2) $S =$ tableSizeとして配列を構築します。

計算量: $O(S\log (\log S))$

operator[]

inline bool operator[](u32 i) const

整数 $i$ が素数であるかを判定します。

制約: $i\ \le\ S$

計算量: 定数時間

isPrime

inline bool isPrime(u32 i) const

整数 $i$ が素数であるかを判定します。

制約: $i\ \le\ S$

計算量: 定数時間

size

inline usize size() const

素数判定できる最大の整数、すなわち $S$ を返します。

計算量: 定数時間

enumeratePrimes

std::vector<u32> enumeratePrimes(u32 N) const

$N$ 以下の素数を昇順に列挙します。

制約: $N\ \le\ S$

計算量: $O(N)$

アルゴリズム

エラトステネスの篩アルゴリズムを利用しています。

エラトステネスの篩アルゴリズム

目標: S 以下の非負整数 i について、 i が素数なら A_i = true 、素数でないなら A_i = false であるような列 A を構築することを考える。

ステップ1: A の全ての要素を \text{true} で初期化する。
ステップ2: A_1 = \text{false}$ とする。
ステップ3: A を昇順に走査する、 A_i が true なら A_{2i}, A_{3i}, A_{4i}, ... に false を代入する。 A_i = false なら何もせず次に進む。
ステップ4: i^2\ >\ S となったら走査を打ち切る。

このアルゴリズムの計算量は $O(S\log (\log S))$ です。素数の逆数和が $O(\log (\log S))$ の発散スピードが $\log (\log S)$ であることが由来しています。

メモ1

$S$ 以下の素数を線形時間で列挙できる線形篩というアルゴリズムが存在します。

じゃあ線形篩を使えよという話になりそうですが、線形篩はテーブルの構築に各整数の最小素因数を必要とします。

本ライブラリでは、 $S$ 以下の整数を約数列挙・素因数分解せよ等といったクエリ処理には線形篩を、素数判定にはエラトステネスの篩を採用する予定です。

メモ2

エラトステネスの篩、線形篩の他にもアトキンの篩や、サンダラムの篩といった素数列挙アルゴリズムがあるそうです。

Depends on

Verified with

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <vector>
#include <cassert>
#include <algorithm>

namespace zawa {

class EratosthenesSieve {
private:
    usize tableSize_;
    std::vector<bool> table_;

public:
    EratosthenesSieve() = default;

    EratosthenesSieve(usize tableSize) : tableSize_{ tableSize + 1 }, table_(tableSize + 1, true) {
        table_.shrink_to_fit();
        assert(tableSize_ > 0);
        table_[0] = table_[1] = false;
        for (u64 i = 2 ; i * i < tableSize_ ; i++) {
            if (!table_[i]) continue;
            for (u64 j = i * i ; j < tableSize_ ; j += i ) {
                table_[j] = false;
            }
        }
    }

    inline bool operator[](u32 i) const {
        assert(i < tableSize_);
        return table_[i];
    }

    inline bool isPrime(u32 i) const {
        assert(i < tableSize_);
        return table_[i];
    }

    inline usize size() const {
        return tableSize_ - 1;
    }

    std::vector<u32> enumeratePrimes(u32 N) const {
        assert(N < tableSize_);
        std::vector<u32> primes{};
        primes.reserve(std::count(table_.begin(), table_.begin() + N + 1, true));
        for (u32 i = 2 ; i <= N ; i++) {
            if (table_[i]) {
                primes.emplace_back(i);
            }
        }
        return primes;
    }
};

} // namespace zawa
#line 2 "Src/Number/EratosthenesSieve.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Number/EratosthenesSieve.hpp"

#include <vector>
#include <cassert>
#include <algorithm>

namespace zawa {

class EratosthenesSieve {
private:
    usize tableSize_;
    std::vector<bool> table_;

public:
    EratosthenesSieve() = default;

    EratosthenesSieve(usize tableSize) : tableSize_{ tableSize + 1 }, table_(tableSize + 1, true) {
        table_.shrink_to_fit();
        assert(tableSize_ > 0);
        table_[0] = table_[1] = false;
        for (u64 i = 2 ; i * i < tableSize_ ; i++) {
            if (!table_[i]) continue;
            for (u64 j = i * i ; j < tableSize_ ; j += i ) {
                table_[j] = false;
            }
        }
    }

    inline bool operator[](u32 i) const {
        assert(i < tableSize_);
        return table_[i];
    }

    inline bool isPrime(u32 i) const {
        assert(i < tableSize_);
        return table_[i];
    }

    inline usize size() const {
        return tableSize_ - 1;
    }

    std::vector<u32> enumeratePrimes(u32 N) const {
        assert(N < tableSize_);
        std::vector<u32> primes{};
        primes.reserve(std::count(table_.begin(), table_.begin() + N + 1, true));
        for (u32 i = 2 ; i <= N ; i++) {
            if (table_[i]) {
                primes.emplace_back(i);
            }
        }
        return primes;
    }
};

} // namespace zawa
Back to top page