质数筛

• 判断一个数是不是质数，最基础的方法:

bool isprime(int n) {
    if(n <= 1) return 0;
    for(int i = 2; i <= sqrt(n); i ++) {
        if(n % i == 0) return 0;
    }
    return 1;
}

这个方法虽然能判断是不是质数，但效率很低，如果要判断的这个数很大，那么多半是会TLE，所以我们需要更高效的算法；

• 埃式筛：

ll is_prime[maxn];  //记录质数 
bool vis[maxn];  //判断是不是质数

void isprime(ll n)
{
	vis[0] = 1;
	ll cnt = 0;  //记录质数个数 
	for(ll i = 2; i <= n; i ++){
		if(!vis[i]){
			is_prime[++cnt] = i;
			for(ll j = 2 * i; j <= n; j += i){
				vis[j] = 1;  //记录质数的倍数是不是质数 
			}
		}
	}
} 

埃式筛就会比普通方法要快得多，但它也有个缺点，就是同一个数会被筛很多次，这导致时间上有所损失，所以有什么办法可以只筛一次呢？当然有：

• 欧拉筛（也称线性筛）

ll is_prime[maxn];  //记录质数 
bool vis[maxn];  //判断是不是质数

void isprime(ll n)
{
	vis[0] = 1;
	ll cnt = 0;  //记录质数个数 
	for(ll i = 2; i <= n; i ++){
		if(!vis[i]){
			is_prime[++cnt] = i;
			if(i <= sqrt(n)){
				for(ll j = i * i; j <= n; j += i){
					vis[j] = 1;  //记录质数的倍数是不是质数 
				}
			}
		}
	}
}