返回目录

每次找小于 $N$ 以下的素数,你是不是都需要花费大半天

别担心！！！筛法来帮忙，它可以迅速的筛选素数，它快到什么程度呢？就这么说，大部分与素数有关的题目用上他，基本上找素数就不用愁了，例如这题

素数环2

那怎么找素数环呢？

都教你筛法了你还想要学链表，你挺狂啊！

筛法的作用就是先从2开始循环，把2往下的倍数打上标签，这样循环到后面就知道3是质数了，然后在往下给3的倍数打标签

代码如下

void ass(int n){
	vis[1]=1;
	for(long long  i=2;i<=n;i++){
		if(!vis[i]){
			cout<<i<<' ';
			cnt++;
			for(long long j=i*i;j<=n;j+=i){
				vis[j]=1;
			}
		}
	}
}