这个有点难理解，我也组织不好语言，再次转发一波。转载出自https://blog.csdn.net/stack_queue/article/details/53560887

求素数是程序设计比赛中经常遇到的问题，最基本的方法是通过素数的定义直接判断，只能被1和它本身整除的数就是素数了。这种方法适合判断单个数是否为素数，当要求一个范围内素数而这个范围又比较大时，这种方法就不太使用了，甚至程序要运行几分钟才能算出结果。

筛法的思想是去除要求范围内所有的合数，剩下的就是素数了，而任何合数都可以表示为素数的乘积，因此如果已知一个数为素数，则它的倍数都为合数。

普通的筛法：

#include
    
     #include
     
      using namespace std;#define MAX 100000//求MAX范围内的素数long long su[MAX],cnt;bool isprime[MAX];void prime(){    cnt=1;    memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数    isprime[0]=isprime[1]=0;//0和1不是素数    for(long long i=2;i<=MAX;i++)    {        if(isprime[i])//保存素数        {            su[cnt++]=i;        }        for(long long j=i*2;j<=MAX;j+=i)//素数的倍数都为合数        {            isprime[j]=0;        }    }}int main(){    prime();    for(long long i=1;i
     
    

普通的线性筛法虽然大大缩短了求素数的时间，但是实际上还是做了许多重复运算，比如2*3=6，在素数2的时候筛选了一遍，在素数为3时又筛选了一遍。如果只筛选小于等于素数i的素数与i的乘积，既不会造成重复筛选，又不会遗漏。时间复杂度几乎是线性的。

优化后的线性筛法：

#include
    
     #include
     
      using namespace std;#define MAX 100000//求MAX范围内的素数long long su[MAX],cnt;bool isprime[MAX];void prime(){    cnt=1;    memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数    isprime[0]=isprime[1]=0;//0和1不是素数    for(long long i=2;i<=MAX;i++)    {        if(isprime[i])            su[cnt++]=i;//保存素数i        for(long long j=1;j
      
     
    

参考：https://blog.csdn.net/Dinosoft/article/details/5829550