library/math/prime-enumerate.hpp

• View this file on GitHub
• Last update: 2023-12-03 13:41:56+08:00
• Include: #include "library/math/prime-enumerate.hpp"

Required by

• library/convolution/gcd-convolution.hpp
• library/convolution/lcm-convolution.hpp
• library/math/divisor-multiple-transform.hpp

Verified with

• test/math/prime-enumerate/yosupo-Enumerate-Primes.test.cpp

Code

#pragma once
#include <vector>

#include <cmath>


namespace felix {

// 2, 3, 5, 7, ...

std::vector<int> prime_enumerate(int N) {
	std::vector<bool> sieve(N / 3 + 1, 1);
	for(int p = 5, d = 4, i = 1, sqn = std::sqrt(N); p <= sqn; p += d = 6 - d, i++) {
		if(!sieve[i]) {
			continue;
		}
		for(int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p, qe = sieve.size(); q < qe; q += r = s - r) {
			sieve[q] = 0;
		}
	}
	std::vector<int> ret{2, 3};
	for(int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++) {
		if(sieve[i]) {
			ret.push_back(p);
		}
	}
	while(!ret.empty() && ret.back() > N) {
		ret.pop_back();
	}
	return ret;
}

} // namespace felix

#line 2 "library/math/prime-enumerate.hpp"
#include <vector>

#include <cmath>


namespace felix {

// 2, 3, 5, 7, ...

std::vector<int> prime_enumerate(int N) {
	std::vector<bool> sieve(N / 3 + 1, 1);
	for(int p = 5, d = 4, i = 1, sqn = std::sqrt(N); p <= sqn; p += d = 6 - d, i++) {
		if(!sieve[i]) {
			continue;
		}
		for(int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p, qe = sieve.size(); q < qe; q += r = s - r) {
			sieve[q] = 0;
		}
	}
	std::vector<int> ret{2, 3};
	for(int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++) {
		if(sieve[i]) {
			ret.push_back(p);
		}
	}
	while(!ret.empty() && ret.back() > N) {
		ret.pop_back();
	}
	return ret;
}

} // namespace felix

Back to top page