结构体运算重定向

1
2
3
4
5
6
7
8
9
struct node {
	int x, w;
	bool operator < (const node& a)const {
		return x < a.x;
	}
	bool operator == (const node& a)const {
		return x == a.x && w == a.w;
	}
};

上式重定向了小于和等于运算符

筛选素数

埃式筛

时间复杂度：nlog(n)

埃式筛就是筛选n以内的素数，从小到大，对每个素数的倍数进行剔除，最后保留下来的就是素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

bool not_prime[N];

vector<int>prime;

int main()
{
    int n;
    cin>>n;//所要筛选的素数的范围
    
    for(int i=2;i*i<=n;i++)
    {
        for(int j=i*i;j<=n;j+=i)not_prime[j]=true;
    }
    
       for(int i=2;i<=n;i++)
       if(!not_prime[i])prime.push_back(i);
}

欧拉筛

时间复杂度： O(n)

算法思路：每个合数都由其最小质因子筛选出来，这样能够保证筛选的线性，每个合数只被筛选一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

bool not_prime[N];

vector<int>prime;

int n;

int main()
{
    cin>>n;
    
    for(int i=2;i<=n;i++)
    {
        if(!not_prime[i])prime.push_back(i);
        
        for(auto j:prime)
        {
            if(j*i>n)break;//这一步不能遗忘
            not_prime[j*i]=true;//这时满足j为j*i的最小质因子
            
            if(i%j==0)break;//当j为i的最小质因子时，若继续向后遍历质数，则那时的j*i不满足以j为最小质因子，会造成重复筛选(虽然对结果没影响）
        }
        
    }
    
    return 0;
}