在OJ刷题经常会遇到的一个问题就是求素数，什么判断素数，判断某个区间有多少个素数。。变着花样考察素数判断，对于要求不是很严格的，我们可以使用素数的定义进行判断，即只能被1和它自身整除的数就是素数了，但是如果过范围比较大，这样就很不实用了，所以引入了筛法求素数，而对于这种方法我们又分为一般筛法和快速线性筛法，对于筛法的思想，比如，求解1~100的素数，手首先从1开始看，1不是素数，所以把它 筛 掉，接下来是2，2是素数，所以，所有2的倍数就不是素数了，我们把4，6，8。。等等都筛掉，然后再看3，3是素数，然后把3的倍数都筛掉。。。以此类推，最后会把所有的合数都筛掉，这也就是这个名字的由来了
一般筛法：
void prime(){
int p[100];
memset(p,0,sizeof(p));
for(int i=2;i<=sqrt(100);i++){
if(!p[i]){ //如果i对应的值是0，那么表示i是素数
for(int j=2;i*j<100;j++){ //从 2*i ，3*i ...标志为1
p[i*j]=1;
}
}
}
for(int i=2;i<100;i++){
if(!p[i]) //值为0，则下标数值为素数
cout<<i<<" ";
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116847.html
