Sieve-of-Eratosthenes(エラトステネスの篩) (math/sieve_of_eratosthenes.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-03-18 15:13:10+09:00

なにこれ

エラトステネスの篩というやつ． 前処理して素数判定を高速にやるなど．

コンストラクタ

• Sieve(n)：$n$ までの篩を前計算する．$n \leq 10^{8}$ 程度．

メンバ関数

• isprime(x)：x が素数であれば trueを，そうでなければ false を返す．
• primefact(n)：n を素因数分解し，$\{素因数,個数\}$ の pair の配列を返す．
• divisorcount(n)：n の約数の個数を返す．

計算量

• Sieve(n)：$O(n)$
• isprime(x)：$O(1)$
• primefact(n)：$O(\log n)$
• divisorcount(n)：$O(\log n)$

参考

• Sieve of Eratosthenes With Linear Time Complexity - Competitive Programming Algorithms

Verified with

• test/aoj_ALDS1_1_C_Sieve.cpp
• test/aoj_NTL_1_A_Sieve.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct Sieve {
private:
	int N;
	vector<int> dv, primes;

public:
	Sieve(int n) : N(n), dv(n + 1, 0) {
		dv[0] = dv[1] = -1;
		for(int i = 2; i <= N; i++) {
			if(!dv[i]) {
				primes.emplace_back(i);
				dv[i] = i;
			}

			for(int p : primes) {
				if(p > dv[i] || (long long)i * p > N) break;
				dv[i * p] = p;
			}
		}
	}

	bool isprime(int x) {
		return dv[x] == x;
	}

	vector<pair<int, int>> primefact(int n) {
		if(n == 1) return vector<pair<int, int>>({});
		vector<pair<int, int>> res = {pair<int, int>(dv[n], 1)};
		n /= dv[n];
		while(n > 1) {
			int d = dv[n];
			if(res.back().first == d) res.back().second++;
			else
				res.emplace_back(d, 1);
			n /= d;
		}
		return res;
	}

	int divisorcount(int n) {
		int res = 1;
		vector<pair<int, int>> flist = primefact(n);
		for(pair<int, int> &p : flist) {
			res *= p.second + 1;
		}
		return res;
	}
};

#line 2 "math/sieve_of_eratosthenes.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct Sieve {
private:
	int N;
	vector<int> dv, primes;

public:
	Sieve(int n) : N(n), dv(n + 1, 0) {
		dv[0] = dv[1] = -1;
		for(int i = 2; i <= N; i++) {
			if(!dv[i]) {
				primes.emplace_back(i);
				dv[i] = i;
			}

			for(int p : primes) {
				if(p > dv[i] || (long long)i * p > N) break;
				dv[i * p] = p;
			}
		}
	}

	bool isprime(int x) {
		return dv[x] == x;
	}

	vector<pair<int, int>> primefact(int n) {
		if(n == 1) return vector<pair<int, int>>({});
		vector<pair<int, int>> res = {pair<int, int>(dv[n], 1)};
		n /= dv[n];
		while(n > 1) {
			int d = dv[n];
			if(res.back().first == d) res.back().second++;
			else
				res.emplace_back(d, 1);
			n /= d;
		}
		return res;
	}

	int divisorcount(int n) {
		int res = 1;
		vector<pair<int, int>> flist = primefact(n);
		for(pair<int, int> &p : flist) {
			res *= p.second + 1;
		}
		return res;
	}
};

Back to top page