Echelon sieve / Euler sieve for prime numbers

At the beginning of the beginning, I recommend two videos, uh, my introductory video (let others go elsewhere for the crumbs (bushi) before I start talking)

Little broken station (well, this teacher is very vivid)

Small broken station (actually I am a fan of this teacher...)

Now if you give us a problem, ask you to find out the [ 1 , L i m i t ] [1,Limit] How to do all the prime numbers in [1,Limit]

First of all, at the very beginning, write down two knowledge points that I always forget

• 0 is not a prime number
• 1 is not a prime number

Satisfied, always forgetting...

The first and easiest to think of is the simple sieve method

we will [ 1 , L i m i t ] [1,Limit] Traverse all the numbers in [1,Limit], and then judge whether they are prime numbers one by one

Because this method is too simple (bushi), so I won’t go into details. Two specific details are put in the code.

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<lli>info;
lli Limit;
bool origin(lli number){
    lli Judge = sqrt(number) + 1;
    //Save this number to avoid repeated calculations. The single number can be determined by i*i, because the sqrt operation is slow
    for(lli temp = 2 ; temp <= Judge ; temp++){
        if(number % temp == 0) return 0;
    }
    return 1;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> Limit;
    info.push_back(2);
    for(lli temp = 3 ; temp <= Limit ; temp += 2){//Multiples of 2 are definitely not prime numbers
        if(origin(temp)) info.push_back(temp);
    }
    return 0;
}

Well, from the road to simplicity, I reward you with a TLE, thank you

Below we will introduce two more optimized sieve methods: Angie sieve/Eulerian sieve

Era_sieve Era_sieve O ( n log ⁡ ( log ⁡ n ) ) O(n\log(\log n)) O(nlog(logn))

We found that a composite number must be obtained by multiplying some prime numbers

So the core of the Escherichia sieve method is: first find a prime number, and then mark the multiples of the prime number
Then after traversing this number, you can judge that it is not a prime number.

Given a simple procedure: L i m i t = 20 Limit = 20 Limit=20

2 { 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 } 2\quad\quad\quad\{4,6,8,10,12,14,16,18,20\} 2{4,6,8,10,12,14,16,18,20}

3 { 6 , 9 , 12 , 15 , 18 } 3\quad\quad\quad\{6,9,12,15,18\} 3{6,9,12,15,18}

4 N o n e 4\quad\quad\quad None 4None

5 { 5 , 10 , 15 , 20 } 5\quad\quad\quad\{5,10,15,20\} 5{5,10,15,20}

... \dots ...

7 { 14 } 7\quad\quad\quad\{14\} 7{14}

⋯ \cdots ⋯

I'm too lazy to go on, I believe it's not hard to understand

Then it's time for happy coding

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli Limit;
vector<lli>info;
bitset<lli(1e8 + 10)> Check;
void Era_sieve(lli Limit){
    for(lli temp = 2 ; temp <= Limit ; temp++){
        if(Check[temp] == 0){
            info.push_back(temp);
            for(lli temp2 = temp*temp; temp2 <= Limit ; temp2 += temp)
                Check[temp2] = 1;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> Limit;
    Era_sieve(Limit);
    return 0;
}

Euler_sieve O ( n ) O(n) O(n)

First of all, we must understand why the Euler algorithm is better. In the previous table, some numbers are assigned repeatedly

For example: let's make a copy of that form

2 { 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 } 2\quad\quad\quad\{4,6,8,10,12,14,16,18,20\} 2{4,6,8,10,12,14,16,18,20}

3 { 6 , 9 , 12 , 15 , 18 } 3\quad\quad\quad\{6,9,12,15,18\} 3{6,9,12,15,18}

4 N o n e 4\quad\quad\quad None 4None

5 { 5 , 10 , 15 , 20 } 5\quad\quad\quad\{5,10,15,20\} 5{5,10,15,20}

... \dots ...

7 { 14 } 7\quad\quad\quad\{14\} 7{14}

⋯ \cdots ⋯

It is not difficult to find that the number 12 12 12, 18 18 18 have been traversed many times, so the Escherichia Sieve method is not linear

So we try to make these numbers only traversed once, so that the linear effect is achieved

For a composite number, we just need to filter it out by the smallest prime number

So we save the number obtained before = from small to large, and then traverse these prime numbers, if this number can be divisible by a certain prime number, then end this cycle

upper code

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli Limit;
vector<lli>info;
bitset<lli(1e8 + 10)> Check;
void Euler_sieve(lli Limit){
    for(lli temp = 2 ; temp <= Limit ; temp++){
        if(Check[temp] == 0) info.push_back(temp);
        for(lli temp2 = 0 ; temp*info[temp2] <= Limit ; temp2++){
            Check[temp*info[temp2]] = 1;
            if(temp % info[temp2] == 0) break;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> Limit;
    Euler_sieve(Limit);
    return 0;
}

end flowering

In addition, I wish CF well tonight, and don't blame me for not writing a note, I'm lazy...