You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/algebra/prime-sieve-linear.md
+13-10Lines changed: 13 additions & 10 deletions
Original file line number
Diff line number
Diff line change
@@ -1,6 +1,6 @@
1
-
<!--?titleSieve of Eratosthenes WithLinearTime Complexity-->
1
+
<!--?title LinearSieve-->
2
2
3
-
#Sieve of Eratosthenes HavingLinearTime Complexity
3
+
#LinearSieve
4
4
5
5
Given a number $n$, find all prime numbers in a segment $[2;n]$.
6
6
@@ -14,7 +14,8 @@ The weakness of the given algorithm is in using more memory than the classic sie
14
14
15
15
Thus, it makes sense to use the described algorithm only until for numbers of order $10^7$ and not greater.
16
16
17
-
The algorithm's authorship appears to belong to Gries & Misra (Gries, Misra, 1978: see references in the end of the article). And, strictly speaking, this algorithm shouldn't be called "sieve of Eratosthenes" since it's too different from the classic one.
17
+
The algorithm's authorship appears to belong to Gries & Misra (Gries, Misra, 1978: see references in the end of the article).
18
+
However it can also be attributed to Euler, and is also known as Euler's Sieve, who already used a similar version of it during his work.
18
19
19
20
##Algorithm
20
21
@@ -43,21 +44,20 @@ The proof of correctness of this algorithm and its runtime can be found after th
43
44
44
45
```cpp
45
46
constint N =10000000;
46
-
int lp[N+1];
47
+
vector<int>lp(N+1);
47
48
vector<int> pr;
48
49
49
-
for (int i=2; i<=N; ++i) {
50
+
for (int i=2; i <=N; ++i) {
50
51
if (lp[i] == 0) {
51
52
lp[i] = i;
52
-
pr.push_back(i);
53
+
pr.push_back(i);
53
54
}
54
-
for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
We can speed it up a bit by replacing vector $pr$ with a simple array and a counter, and by getting rid of the second multiplication in the nested`for` loop (for that we just need to remember the product in a variable).
60
-
61
61
## Correctness Proof
62
62
63
63
We need to prove that the algorithm sets all values $lp []$ correctly, and that every value will be set exactly once. Hence, the algorithm will have linear runtime, since all the remaining actions of the algorithm, obviously, work for $O (n)$.
@@ -76,7 +76,10 @@ Hence, the algorithm will go through every composite number exactly once, settin
76
76
77
77
## Runtime and Memory
78
78
79
-
Although the running time of $O(n)$ is better than $O(n \log \log n)$ of the classic sieve of Eratosthenes, the difference between them is not so big. In practice that means just double difference in speed, and the optimized versions of the sieve run as fast as the algorithm given here.
79
+
Although the running time of $O(n)$ is better than $O(n \log \log n)$ of the classic sieve of Eratosthenes, the difference between them is not so big.
80
+
In practice the linear sieve runs about as fast as a typical implementation of the sieve of Eratosthenes.
81
+
82
+
In comparison to optimized versions of the sieve of Erathosthenes, e.g. the segmented sieve, it is much slower.
80
83
81
84
Considering the memory requirements of this algorithm - an array $lp []$ of length $n$, and an array of $pr []$ of length $\frac n {\ln n}$, this algorithm seems to worse than the classic sieve in every way.