C/C++线性筛素数的三种方法

一、埃拉托斯特尼筛法

基本思想：素数的倍数一定不是素数

实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。

说明：整数1特殊处理即可。背过就好了。

时间复杂度O（nlogn）

空间复杂度为O(n)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000001;
int vis[maxn];
void prime(int );


int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	prime(n);
	for(int i = 1;i <= m;++i){
		int x;
		scanf("%d",&x);
		if(vis[x]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
void prime(int n){
	for(int i = 0;i < n;++i) vis[i] = true;
	vis[0] = vis[1] = 0;
	for(int i = 2;i * i < n;++i) {
		if (!vis[i]) continue;
		for (int j = i; i * j < n; j++) vis[ i*j ] = 0;
	}
}

二、欧拉筛法（线性筛法）

时间复杂度O（n）

空间复杂度O（n）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> 
using namespace std;
void is_prime(int);

const int maxn(100001);
int prime[maxn];
bool vis[maxn];
int tot;

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	is_prime(n);
	for(int i=1;i<=m;++i){
		int x;
		scanf("%d",&x);
		if(vis[x]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}


void is_prime(int list)
{
    memset(vis,true,sizeof(vis));
    vis[1]=false;
    for(int i=2;i<=list;++i){
        if(vis[i]) prime[++tot]=i;
        for(int j=1;j<=list&&i*prime[j]<=list;++j){
           vis[i*prime[j]]=false;
           if(i%prime[j]==0) break;
        }
    }
}

三、一个奇怪的筛法

时间复杂度 接近O(n)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> 
using namespace std;

const int maxn(10000005);
bool he[maxn]; 
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    he[0]=he[1]=1;
    int t;
    for(int i=4;i<=n;i+=2) he[i]=1;
    for(int i=2;i<=n;i++)
        if(!he[i])
            for(int j=i*2;j<=n;j+=i)
                he[j]=1;
    for(int i=1;i<=m;i++){
        scanf("%d",&t);
        if(he[t]) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

洛谷：P3383