tags | e_maxx_link | |
---|---|---|
|
prime_sieve_linear |
Given a number
The standard way of solving a task is to use the sieve of Eratosthenes. This algorithm is very simple, but it has runtime
Although there are a lot of known algorithms with sublinear runtime (i.e. $o(n)$), the algorithm described below is interesting by its simplicity: it isn't any more complex than the classic sieve of Eratosthenes.
Besides, the algorithm given here calculates factorizations of all numbers in the segment
The weakness of the given algorithm is in using more memory than the classic sieve of Eratosthenes': it requires an array of
Thus, it makes sense to use the described algorithm only until for numbers of order
The algorithm is due to Paul Pritchard. It is a variant of Algorithm 3.3 in (Pritchard, 1987: see references in the end of the article).
Our goal is to calculate minimum prime factor
Besides, we need to store the list of all the found prime numbers - let's call it
We'll initialize the values
Now we'll go through the numbers from 2 to
-
$lp[i] = 0$ - that means that$i$ is prime, i.e. we haven't found any smaller factors for it.
Hence, we assign$lp [i] = i$ and add$i$ to the end of the list$pr[]$ . -
$lp[i] \neq 0$ - that means that$i$ is composite, and its minimum prime factor is$lp [i]$ .
In both cases we update values of
Let's consider numbers
We'll set a new value
The proof of correctness of this algorithm and its runtime can be found after the implementation.
const int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;
for (int i=2; i <= N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back(i);
}
for (int j = 0; i * pr[j] <= N; ++j) {
lp[i * pr[j]] = pr[j];
if (pr[j] == lp[i]) {
break;
}
}
}
We need to prove that the algorithm sets all values
Notice that every number
where
Now, let's compare this with the actions of our algorithm: in fact, for every
Hence, the algorithm will go through every composite number exactly once, setting the correct values
Although the running time of
In comparison to optimized versions of the sieve of Erathosthenes, e.g. the segmented sieve, it is much slower.
Considering the memory requirements of this algorithm - an array
However, its redeeming quality is that this algorithm calculates an array
Knowing the factorizations of all numbers is very useful for some tasks, and this algorithm is one of the few which allow to find them in linear time.
- Paul Pritchard, Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987), pp.17-35.