lib/functions/eratisthenes.cpp

View this file on GitHub
Last update: 2019-11-30 20:08:52+09:00

Code

auto eratosthenes = []{
	constexpr int N = 2e6;
	bitset<N> not_prime(3);
	for(int i = 2; i < N; ++i)
		if(!not_prime[i])
			for(int j = 2 * i; j < N; j += i)
				not_prime.set(j);
	return not_prime;
};

#line 1 "lib/functions/eratisthenes.cpp"
auto eratosthenes = []{
	constexpr int N = 2e6;
	bitset<N> not_prime(3);
	for(int i = 2; i < N; ++i)
		if(!not_prime[i])
			for(int j = 2 * i; j < N; j += i)
				not_prime.set(j);
	return not_prime;
};