线性筛素数 模板

题目介绍

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。

方法一: 埃筛

时间复杂度 $O(nlog(n))$

主要思路: 质数的倍数肯定不是质数

#include<bits/stdc++.h>
using namespace std;

const int N = 1e7+10;
bool vis[N];
int n,m,k;

void prime(int n){
	for(int i=2;i<=sqrt(n);i++)
		if(!vis[i])
			for(int j=2;j<=n/i;j++)
				vis[i*j] = true;
} 

int main(){
	scanf("%d%d",&n,&m);
	// pre
	vis[0] = 1;
	vis[1] = 1;
	prime(n);
	while(m--){
		scanf("%d",&k);
		printf("%s\n", vis[k]?"No":"Yes");
	}
}

方法二: 欧拉筛

时间复杂度: $O(n)$ 真正的线性筛

主要思路：可以从代码中看出来，它比上面的筛法去掉了重复计算

#include<bits/stdc++.h>
using namespace std;

const int N = 1e7+10;

bool isprime[N];
int prime[N];
int cnt = 0;

void get_prime(int n){
	memset(isprime, 1, sizeof(isprime));
	isprime[1] = 0;

	for(int i=2;i<=n;i++){
		if(isprime[i])
			prime[++cnt] = i;
		for(int j=1;j<=cnt && i*prime[j]<=n;j++){
			isprime[i*prime[j]] = 0;
			if(i%prime[j]==0)
				break;
		}
	}
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	get_prime(n);
	int t;
	while(m--){
		scanf("%d",&t);
		if(isprime[t])
			printf("Yes\n");
		else
			printf("No\n");
	}
}