筛素数

// 1：这是最原始的筛法，还有待优化   #define Max 1000000  bool prime[Max];  void IsPrime(){       prime[0]=prime[1]=0;prime[2]=1;  for(int i=3;i<max;i++)          prime[i]=i%2==0?0:1;  int t=(int)sqrt(Max*1.0);  for(int i=3;i<=t;i++)  if(prime[i])  for(int j=i;j<Max;j+=i)              prime[j]=0;  }  

 

//2：优化后的筛法，手动地模拟原始筛法就可以发现，某个数字可能被不止一次地删去  //   优化后的筛法就可以避免这种不必要的删去操作   #define Max 1000000  bool prime[Max];  void IsPrime(){       prime[0]=prime[1]=0;prime[2]=1;  for(int i=3;i<max;i++)          prime[i]=i%2==0?0:1;  int t=(int)sqrt(Max*1.0);  for(int i=3;i<=t;i++)  if(prime[i])  for(int j=i*i;j<Max;j+=2*i)//优化               prime[j]=0;  }

 

//与前两种筛法不同，此种筛法中prime[i]=2*i+3（即：我们只存储奇数，偶数肯定不是素数的）   #define Max 1000000  bool prime[Max>>1];  void IsPrime(){       memset(prime,true,sizeof(prime));  int n=Max>>1,m=(int)(sqrt(Max*1.0)/2.0);  for(int i=0;i<=m;i++)          if(prime[i])  for(int j=2*i*i+6*i+3;j<=n;j+=2*i+3)              isprime[j]=false;  }  

 

转载于:https://www.cnblogs.com/DukeLv/p/7894805.html