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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-12 16:54:24+09:00
• Include: #include "src/math/sieve_of_eratosthenes.hpp"

Verified with

• test/math/sieve_of_eratosthenes/aoj_1276.test.cpp
• test/math/sieve_of_eratosthenes/aoj_itp1_3_d.test.cpp

Code

#ifndef MATH_SIEVE_OF_ERATOSTHENES
#define MATH_SIEVE_OF_ERATOSTHENES

#include <numeric>
#include <utility>
#include <vector>

class SieveOfEratosthenes {
private:
	std::vector<int> min_factor;

public:
	SieveOfEratosthenes(int n) : min_factor(n + 1) {
		std::iota(min_factor.begin(), min_factor.end(), 0);
		for (int p = 2; p * p <= n; ++p) {
			if (min_factor[p] < p) continue;
			for (int q = p * p; q <= n; q += p) {
				if (min_factor[q] == q) min_factor[q] = p;
			}
		}
	}

	bool is_prime(int n) { return n > 1 && min_factor[n] == n; }

	std::vector<std::pair<int, int>> factorize(int n) {
		std::vector<std::pair<int, int>> res;
		while (n > 1) {
			int p = min_factor[n];
			int exp = 0;
			while (min_factor[n] == p) {
				n /= p;
				++exp;
			}
			res.emplace_back(p, exp);
		}
		return res;
	}

	std::vector<int> divisor(int n) {
		std::vector<int> res{1};
		for (auto const &[p, exp] : factorize(n)) {
			int sz = res.size();
			for (int i = 0; i < sz; ++i) {
				int x = 1;
				for (int j = 0; j < exp; ++j) {
					x *= p;
					res.push_back(res[i] * x);
				}
			}
		}
		return res;
	}
};

#endif // MATH_SIEVE_OF_ERATOSTHENES

#line 1 "src/math/sieve_of_eratosthenes.hpp"



#include <numeric>
#include <utility>
#include <vector>

class SieveOfEratosthenes {
private:
	std::vector<int> min_factor;

public:
	SieveOfEratosthenes(int n) : min_factor(n + 1) {
		std::iota(min_factor.begin(), min_factor.end(), 0);
		for (int p = 2; p * p <= n; ++p) {
			if (min_factor[p] < p) continue;
			for (int q = p * p; q <= n; q += p) {
				if (min_factor[q] == q) min_factor[q] = p;
			}
		}
	}

	bool is_prime(int n) { return n > 1 && min_factor[n] == n; }

	std::vector<std::pair<int, int>> factorize(int n) {
		std::vector<std::pair<int, int>> res;
		while (n > 1) {
			int p = min_factor[n];
			int exp = 0;
			while (min_factor[n] == p) {
				n /= p;
				++exp;
			}
			res.emplace_back(p, exp);
		}
		return res;
	}

	std::vector<int> divisor(int n) {
		std::vector<int> res{1};
		for (auto const &[p, exp] : factorize(n)) {
			int sz = res.size();
			for (int i = 0; i < sz; ++i) {
				int x = 1;
				for (int j = 0; j < exp; ++j) {
					x *= p;
					res.push_back(res[i] * x);
				}
			}
		}
		return res;
	}
};

Back to top page