I want to know what is euler sieve and how it works in O(N) complexity, I read this but don’t know how I code …can someone help or explain (or share some resource)
@galencolin
2 Likes
Codeforces blog -
The second link contains the linear sieve.
1 Like
so it’s better to use linear sieve OR sieve of Eratosthenes …
Can u give some questions where classical sieve give tle or some other thing and linear sieve perfectly works ( that’s how i compare )
I think that question will give TLE in normal sieve.
no it will easily AC
bool prime[MAX+1];
vi mp;
void sieve1(){ //prime or not
for(int i=0;i<=MAX;i++) prime[i]=1;
prime[0]=prime[1]=0;
for(lli i=4;i<=MAX;i+=2) prime[i]=0;
for (int p=3; p*p<=MAX; p+=2)
if (prime[p] == 1)
for (int i=p*2; i<=MAX; i += p)
prime[i] = 0;
mp.pb(2);
for(lli i=3;i<=MAX-1;i+=2)
if(prime[i]) mp.pb(i);
}
for(lli i=0;i<sz(mp);i+=100)
cout<<mp[i]<<"\n";
std::vector <int> prime;
bool is_composite[MAXN];
void sieve (int n) {
std::fill (is_composite, is_composite + n, false);
for (int i = 2; i < n; ++i) {
if (!is_composite[i]) prime.push_back (i);
for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
is_composite[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
As is shown in the code, the statement if (i % prime[j] == 0) break; terminates the loop when p divides i. From the analysis above, we can see that the inner loop is executed only once for each composite. Hence, the code above performs in O(n) complexity, resulting in its name — the ‘linear’ sieve.
Ok for each non prime the inner loop traverse only a time right ?
But for a prime number (let say 7) the inner loop is iterating (number of primes before 7 ie., 3 ) 3 times … so how the time complexity is O(N) ?
@galencolin @hello_hell @gaurang1996
Now that someone has brought up the topic, I’d like to bring this question into limelight. I think the article on Wikipedia talks about Wheel of Factorization with a modulus that covers all numbers in the range. Linear Sieve is different, and the proof is easily available online, for example, you can go through the cp-algorithms article which was already posted above by @hello_hell 
2 Likes
Yeah there may be some difference between wheel factorisation and Linear sieve(or euler sieve) … so please explain someone 
I’ll try to write an explanation if you can wait 
Introduction:
Here’s the classic implementation, call it the vanilla sieve (i.e. without any dilutions):
auto sieve(int n) {
vector<bool> p(n + 1, true);
p[0] = p[1] = false;
for(int i = 2; i < n / i; ++i) if(p[i]) {
for(int j = i * i; j <= n; j += i) p[j] = false;
}
vector<int> prime;
for(int i = 2; i <= n; ++i) if(p[i]) prime.emplace_back(i);
return move(prime);
}
The only optimizations at the moment, as can be seen, is iterating till the square root in the outer loop, and iterating from the multiple that is the square in the inner loop. In the outer loop, we go through the numbers that are the candidates for being a prime, in the hope that when we actually hit a prime, we’ll mark its multiples in the given range in the inner loop. So, just keep in mind that the outer loop passes through candidate primes and the inner, through multiples of actual primes. Every number from the outer loop that doesn’t pass the if statement corresponds to a wasted operation in the sense that the algorithm can skip those iterations without compromising correctness. Similarly, every multiple of the prime in the inner loop that has previously been marked by an earlier prime corresponds to a wasted operation in the same sense. Evidently, there is a lot of redundant work. It provides a motivation for algorithms that tends to eliminate this redundancy (with varying degrees), including Linear Sieve and Wheel of Factorization. Well, then.
ok lets see how it works, but before that i wanna clear, the benchmarks of linear sieve are not that significant as it uses 32 times more memory,so its always better to use normal sieve.
Now first let assume its not linear that is it must be visiting or changing the boolean of each number or most of the number upto n at least log n times or somewhere around that, lets fix the statement as our assumption for the contradiction, but is it gonna happen, as in normal sieve each number gets visited for (its total number of distinct prime factors) times, but in linear sieve we have already stored the primes before hand, so the(i % prime[j] == 0 ) break condition makes sure, each i will get visited at most once i.e., only one prime factor for each number,because of jumping out. which makes it linear.
1 Like
your implementation is wrong i guess, it should be,
auto sieve(int n) {
vector<bool> p(n + 1, true);
p[0] = p[1] = false;
for(int i = 2; i < n / i; ++i) if(p[i]) {
for(int j = 2; j*i <= n; ++j) p[j*i] = false;
}
vector<int> prime;
for(int i = 2; i <= n; ++i) if(p[i]) prime.emplace_back(i);
return move(prime);
}
Oops, there was a typo. I edited it, thanks for pointing out 
Wheel of Factorization:
You might have been familiar with the following optimization:
auto sieve(int n) {
vector<bool> p(n + 1, true);
p[0] = p[1] = false;
for(int i = 3; i < n / i; i += 2) if(p[i]) {
for(int j = i * i, k = i << 1; j <= n; j += k) p[j] = false;
}
vector<int> prime{2};
for(int i = 3; i <= n; i += 2) if(p[i]) prime.emplace_back(i);
return move(prime);
}
We exploit the fact that 2 is the only even prime so we can eliminate all even numbers greater than that from being a candidate in the outer loop. As a result, it runs from 3 and skips every even number. Similarly, in the inner loop, we skip every even multiple of the selected prime. Notice that even in post-processing, we don’t need to make the loop pass through any even number (so that takes care of the fact that we never actually marked an even number as non-prime). Consequently, we have eliminated 50% of the redundant work by just this observation. If only, we can extend this… Well, turns out that we can! In fact, the generalization of this observation is exactly what Wheel of Factorization is.
The idea is this: we select an initial set of numbers, the basis (generally, the first few prime numbers). Using this, we mark off all the numbers which can be divided by at least one number in the basis. What we are left with are all the numbers that are co-prime with the elements of the basis. These will form the candidates to be used in the outer loop. I’ll continue with an example. Say our basis, B = {2, 3, 5}. Now, LCM(B) = 30. So, we can have 30 different remainders (0 - 29) representing all natural numbers. Out of these, we cancel all such remainders (and hence classes of numbers) that are divisible by at least one of 2, 3, or 5. What we are left with is this set W = {1, 7, 11, 13, 17, 19, 23, 29} which are the remainder classes co-prime with the basis. This set is called the wheel, and its elements, not surprisingly, are called spokes. The LCM is sometimes called the modulus or the circumference of the wheel.
Enough theory, now let’s get concrete. Here’s an implementation of the wheel, modulo 30:
auto sieve(int n) {
vector<bool> p(n + 1, true);
p[0] = p[1] = false;
int skip[] = {6, 4, 2, 4, 2, 4, 6, 2};
map<int, int> wheel = {{1, 0}, {7, 1}, {11, 2}, {13, 3}, {17, 4}, {19, 5}, {23, 6}, {29, 7}};
for(int i = 7, j = 1; i <= n / i; i += skip[j], j = (j + 1) % 8) {
if(p[i]) {
for(int k = i * i, l = wheel[i % 30]; k <= n; k += i * skip[l], l = (l + 1) % 8) {
p[k] = false;
}
}
}
vector<int> prime{2, 3, 5};
for(int i = 7, j = 1; i <= n; i += skip[j], j = (j + 1) % 8) {
if(p[i]) prime.emplace_back(i);
}
return move(prime);
}
The skip array contains the difference between the spokes, which we use to jump through the numbers in the outer loop, and through the multiples in the inner loop. Since we used 2, 3, and, 5 on our basis: we assume that we marked off all their multiples and hence we start with 7 (note this is the first number after 1 in the wheel, and that 1 will always be on the wheel since it’s co-prime with everything). After that, we use the skip-list to jump through numbers with the remainders in the wheel in the outer loop: I used a map to convert between remainders and indices of the skip-list. In the inner loop too, we go through only those multiples that have remainders in the skip-list (starting from the ith multiple). Finally, we initialize the primes list with the basis and traverse the loop in a similar manner in post-processing. Working modulo 30, we only have to jump through 8 (the size of the wheel) / 30 (the circumference) of the numbers which is about 26% of the actual range!
This might seem like a constant-factor optimization but it drastically reduces the runtime as you extend it to modulo 210 and higher (though the benefit grows quite slowly after that). Finally, its asymptotic complexity is O(N / log(log(N))) according to the paper which popularized the method
References:
P.S. If you want an implementation with a higher modulus (and even a generic one), here’s the link.
7 Likes
+1 for the question.
This loop breaks when i % prime[ j ] =0 means i divisible by any prime present in prime vector , means i == prime[ j ] right?
For ex : i = 19(which is prime)
and in prime vector we have(2,3,5,7,11,13,17,19)
so in is_composite following indexes marked as true -
19*2 , 19 * 3 , 19 * 5 , 19 * 7 , 19 * 11, 19 * 13, 19 * 17, 19 * 19 and now 19 is divisble by 19 so it breaks …
Next prime is 23 so in is_composite following indexes marked as true -
23 * 2 23 * 3 23 * 5 and so on…
So how this becomes linear?