linearSieve (線形篩・素因数分解/約数列挙)
(src/math/linearSieve.hpp)

• View this file on GitHub
• Last update: 2023-03-04 23:54:34+09:00
• Include: #include "src/math/linearSieve.hpp"

概要

線形篩のアルゴリズムにより、 入力で与えた非負整数 $n$ 以下の最小素因数を列挙します。

素因数分解や約数列挙のクエリがたくさん飛んでくる場合や、素因数で小さいサイズにしていくタイプの動的計画法で利用できたりします。

機能

コンストラクタ

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

(1)

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

(2)

1以上n以下の最小素因数を列挙する

• 計算量 : $O(n)$

メンバ関数

factorize

std::vector<std::pair<int, int>> factorize(int x)

$x$ を素因数分解する。

• (first, second) = 素因数、次数である

制約

$1\ \le\ x\ \le\ n$

計算量

$O(\log x)$ (多分 <- カス!)

divisor

std::vector<int> divisor(int x)

$x$ の約数を列挙する

• 結果が昇順に並んでいないことに注意！

制約 :

$1\ \le\ x\ \le\ n$

計算量

$O(\log^2 x)$ (多分 <- カス!)

• 実装がカス！なのでlogが一個多めについてます。多分(カス！)

enumPrime

std::vector<int> enumPrime()

• $n$ 以下の素数を昇順に列挙したものを返します。

isPrime

bool isPrime(int x)

$x$ が素数かを判定します。

制約

$1\ \le\ x\ \le\ n$

計算量

O(1)$

numPrime

int numPrime()

$n$ 以下の素数の個数を返します

計算量

$O(1)$

operator

[]

int [](int x)

$x$ の最小素因数を返します。

制約

$1\ \le\ x\ \le\ n$

計算量

$O(1)$

参考

線形篩

Verified with

• test/ABC170-D.test.cpp
• test/ABC177-E.test.cpp
• test/ABC250-D.test.cpp
• test/ABC254-D.test.cpp
• test/ABC292-C.test.cpp

Code

#pragma once

#include <vector>
#include <utility>

namespace zawa {

class linearSieve {
private:
	std::vector<int> divs;
	std::vector<int> primes;

public:
	linearSieve() {}
	linearSieve(std::size_t n) : divs(n + 1, 1) {
		for (std::size_t i = 2 ; i < n + 1 ; i++) {
			if (divs[i] == 1) {
				divs[i] = i;
				primes.push_back((int)i);
			}
			for (const auto& p : primes) {
				if (p * i > n or p > divs[i]) {
					break;
				}
				divs[p * i] = p;
			}
		}
	}

	std::vector<std::pair<int, int>> factorize(int x) {
		std::vector res(0, std::pair(0, 0));
		while (x > 1) {
			res.emplace_back(divs[x], 0);
			while (divs[x] == res.back().first) {
				x /= divs[x];
				res.back().second++;
			}
		}
		return res;
	}

	std::vector<int> divisor(int x) {
		std::vector res(1, 1);
		for (const auto& [p, q] : factorize(x)) {
			std::size_t now = res.size();
			for (std::size_t i = 0 ; i < now ; i++) {
				int mul = p;
				for (int _ = 0 ; _ < q ; _++) {
					res.emplace_back(res[i] * mul);
					mul *= p;
				}
			}
		}
		return res;
	}

	std::vector<int> enumPrime() {
		return primes;
	}

	int numPrime() {
		return (int)primes.size();
	}

	bool isPrime(int x) {
		return (x != 0 and x != 1 and divs[x] == x);
	}

	int operator[](int x) {
		return divs[x];
	}
};

}

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

#include <vector>
#include <utility>

namespace zawa {

class linearSieve {
private:
	std::vector<int> divs;
	std::vector<int> primes;

public:
	linearSieve() {}
	linearSieve(std::size_t n) : divs(n + 1, 1) {
		for (std::size_t i = 2 ; i < n + 1 ; i++) {
			if (divs[i] == 1) {
				divs[i] = i;
				primes.push_back((int)i);
			}
			for (const auto& p : primes) {
				if (p * i > n or p > divs[i]) {
					break;
				}
				divs[p * i] = p;
			}
		}
	}

	std::vector<std::pair<int, int>> factorize(int x) {
		std::vector res(0, std::pair(0, 0));
		while (x > 1) {
			res.emplace_back(divs[x], 0);
			while (divs[x] == res.back().first) {
				x /= divs[x];
				res.back().second++;
			}
		}
		return res;
	}

	std::vector<int> divisor(int x) {
		std::vector res(1, 1);
		for (const auto& [p, q] : factorize(x)) {
			std::size_t now = res.size();
			for (std::size_t i = 0 ; i < now ; i++) {
				int mul = p;
				for (int _ = 0 ; _ < q ; _++) {
					res.emplace_back(res[i] * mul);
					mul *= p;
				}
			}
		}
		return res;
	}

	std::vector<int> enumPrime() {
		return primes;
	}

	int numPrime() {
		return (int)primes.size();
	}

	bool isPrime(int x) {
		return (x != 0 and x != 1 and divs[x] == x);
	}

	int operator[](int x) {
		return divs[x];
	}
};

}

Back to top page