素数筛

##素数##
素数即质数，只能被自身和一整除。
一般暴力找素数，O(n2)或者O(nsqrt(n))
这样耗费时间太多，所以我们用筛法来处理
##素数筛##
素数筛通过将非素数筛掉来找素数，是重要的数论工具
###一般筛法### --埃氏筛
一般筛法接近O（n）的复杂度，但比快速筛慢

bool mark[Max];//标记是否为素数
int ss[Max];//将素数存入数组
void prime()//筛法
{
	memset(mark,0,sizeof(mark);
	int tot=0;
	for(int i=2;i<Max;i++)
	{
		if(!mark[i])
		{
			ss[tot++]=i;
			for(int j=2*i;j<Max;j+=i)//筛掉素数的倍数
			mark[j]=1;
		}
	}
}

###快速筛法###
快速筛法的复杂度一般为O(n） --线性筛

bool mark[Max];//标记是否为素数
int ss[Max];//将素数存入数组
void prime()//筛法
{
	memset(mark,0,sizeof(mark);
	int tot=0;
	for(int i=2;i<Max;i++)
	{
		if(!mark[i])ss[tot++]=i;
		for(int j=0;j<tot&&i*ss[j]<Max;j++)
		{
			mark[i*ss[j]=1;
			if(i%ss[j]==0）break;//保证筛过的非素数只筛一次
		}
	}
}