【数论】判素数与素数筛法

判断素数

int is_prime(int n){
    if(n==1)return 0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}

普通筛

int p[MS];
memset(p,0,sizeof p);
for(int i=2;i<=MS;i++) p[i] = 1;
for(int i=2;i<=sqrt(MS);i++){
	if(p[i]){
		for(int j=i+i;j<=MS;j+=i)
			p[j] = 0;
	}
}
// 标记为 1 的即为素数 

欧拉筛

int prime[MS];      //就是个素数表, prime[] = {0,2,3,5,7...};
bool sf[MS]; //判断这个数是不是素数，sf[i]中的i是从1到maxn的数
Void Euler_sieve(){
	//num 用来记筛到第几个质数
	memset(sf,true,sizeof(sf));
	for(int i=2; i<=MS; i++) {       //外层枚举1~maxn
		if(sf[i]) prime[++num]=i;      //如果是质数就加入素数表
		for(int j=1; j<=num; j++) {    //内层枚举num以内的质数
			if(i*prime[j]>MS) break; //筛完结束
			sf[i*prime[j]]=false;      //筛掉...
			if(i%prime[j]==0) break;   //避免重复筛
		}
	}
	sf[1]=false;
	sf[0]=false;  //1 0 特判
}