luogu3383 【模板】线性筛素数

如果prime[i]是k的因子，那么【k * （在prime[i]以后的质数）】等于【prime[i]*（k/prime[i]）*（这个质数）】，一定被筛过了，所以这里可以break。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

bool isp[10000005];

int n, m, cnt, pri[10000005], uu;

int main(){

	cin>>n>>m;

	memset(isp, true, sizeof(isp));

	isp[0] = isp[1] = false;

	for(int i=2; i<=n; i++){

		if(isp[i])	pri[++cnt] = i;

		for(int j=1; j<=cnt; j++){

			if(i*pri[j]>n)	break;

			isp[i*pri[j]] = false;

			if(i%pri[j]==0)	break;

		}

	}

	for(int i=1; i<=m; i++){

		scanf("%d", &uu);

		if(isp[uu])	printf("Yes\n");

		else 		printf("No\n");

	}

	return 0;

}

巴特西

luogu3383 【模板】线性筛素数

最新文章

热门文章