primeSieve (エラトステネスの篩）
(src/math/primeSieve.hpp)

View this file on GitHub
Last update: 2023-03-05 22:25:53+09:00
Include: #include "src/math/primeSieve.hpp"

概要

エラトステネスの篩アルゴリズムによりある正整数 $n$ 以下の正整数についてそれが素数かそうでないかの是非を保持します。

osa-k法等の高速素因数分解、高速約数列挙をしたい場合は線形篩の方をお使いください

機能

コンストラクタ

(1) zawa::primeSieve() 
(2) zawa::primeSieve(std::size_t n)

(1)

デフォルトコンストラクタ

(2)

n以下の正整数について素数判定を行う

計算量

$O(n\log (\log n))$

operator

[]

inline bool operator[](std::size_t i) const

$i$ が素数かどうかをbool値で返す

制約

$0\ <\ i\ \le\ n$

計算量

$O(1)$

メモ

今までテーブルの構築を

for (usize i = 2 ; i <= n ; i++) 
	if (table[i])
		for (usize j = i * i ; j <= n ; j += i)
			table[j] = false;

とやっていたが、なぜかコドフォで壊れた(LCやAtCでは普通に大丈夫）

ので

for (usize i = 2 ; i <= n ; i++)
	if (table[i])
		for (usize j = i * 2 ; j <= n ; j += i)
			table[j] = false;

としている。個人的な予想ではusize (=std::size_t)がなんか悪さしとる

参考

エラトステネスの篩の活用法を総特集！〜高速素因数分解・メビウスの反転公式〜

Required by

Verified with

Code

#pragma once

#include <vector>

namespace zawa {

class primeSieve {
private:
	std::vector<bool> sieve;

public:
	primeSieve() {}
	primeSieve(std::size_t n) : sieve(n + 1, true) {
		if (n >= 0) {
			sieve[0] = false;
		}
		if (n >= 1) {
			sieve[1] = false;
		}
		for (std::size_t i = 2 ; i <= n ; i++) {
			if (sieve[i]) {
				for (std::size_t j = i * 2 ; j <= n ; j += i) {
					sieve[j] = false;
				}
			}
		}
	}

	inline bool operator[](std::size_t i) const {
		return sieve[i];
	}

	inline std::size_t size() const {
		return sieve.size();
	}
};

}// namespace zawa

#line 2 "src/math/primeSieve.hpp"

#include <vector>

namespace zawa {

class primeSieve {
private:
	std::vector<bool> sieve;

public:
	primeSieve() {}
	primeSieve(std::size_t n) : sieve(n + 1, true) {
		if (n >= 0) {
			sieve[0] = false;
		}
		if (n >= 1) {
			sieve[1] = false;
		}
		for (std::size_t i = 2 ; i <= n ; i++) {
			if (sieve[i]) {
				for (std::size_t j = i * 2 ; j <= n ; j += i) {
					sieve[j] = false;
				}
			}
		}
	}

	inline bool operator[](std::size_t i) const {
		return sieve[i];
	}

	inline std::size_t size() const {
		return sieve.size();
	}
};

}// namespace zawa

primeSieve (エラトステネスの篩） (src/math/primeSieve.hpp)

概要

機能