Linear Sieve
(library/number-theory/linear-sieve.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/number-theory/linear-sieve.hpp"

Linear Sieve

Computes all the primes less than $N$ in $\mathcal O(N)$ time.

The way it works is it crosses out composite numbers exactly once by checking by smallest prime factors. In this manner, it is possible to compute multiplicative functions for all $N$ in a range in linear time, as shown in the CF blog post under resources.

Resources

• Codeforces

Verified with

• verify/spoj/spoj-TDKPRIME.test.cpp

Code

#pragma once

template <int N> struct LinearSieve {
	std::bitset<N> pri;
	std::vector<int> pr;
	
	LinearSieve() {
		pri.set();
		pri[0] = pri[1] = 0;
		for (int i = 2; i < N; ++i) {
			if (pri[i]) 
				pr.push_back(i);
			for (int j = 0; j < (int)pr.size() && i * pr[j] < N; ++j) {
				pri[i * pr[j]] = 0;
				if (i % pr[j] == 0) 
					break;
			}
		}
	}
};

template <int N> struct LinearSieve {
	std::bitset<N> pri;
	std::vector<int> pr;
	
	LinearSieve() {
		pri.set();
		pri[0] = pri[1] = 0;
		for (int i = 2; i < N; ++i) {
			if (pri[i]) 
				pr.push_back(i);
			for (int j = 0; j < (int)pr.size() && i * pr[j] < N; ++j) {
				pri[i * pr[j]] = 0;
				if (i % pr[j] == 0) 
					break;
			}
		}
	}
};

Back to top page