筛选法求素数

链接

    算法操作过程：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。

代码：求N以内的素数

 

[cpp] view plaincopyprint?   #include<iostream>     #include<cstring>     using namespace std;    const int MAX=10000;    bool prime[MAX];    void IsPrime()  {      memset(prime,true,sizeof(prime));      prime[1]=false;      prime[2]=true;      for(int i=2;i<=MAX;i++)      {          if(prime[i]==true)          {              for(int j=i;j<=MAX;j+=i)              {                   prime[j]=false;              }              prime[i]=true;          }      }  }  int main()  {      int N;      IsPrime();      cin>>N;      for(int i=1;i<=N;i++)          if(prime[i]==true)              cout<<i<<endl;  }    

转载于:https://www.cnblogs.com/AllenDuane/p/3746976.html

相关资源：基于Jupyter 使用列表实现筛选法求素数（python）