素数筛法的关键就在一个“筛”字。算法从小到大枚举所有数，对每一个素数，筛去它的所有倍数，剩下的就都是素数了。

　　例如：求1-15中的所有素数。

　　1、  2是素数（唯一需要事先确定的），因此筛去2的所有倍数，即4、6、8、10、12、14；

　　2、  3没有被前面的步骤筛去，因此3是素数，筛去所有3的倍数，即6，9，12，15；

　　3、  4已经在1中被筛去，因此4不是素数；

　　4、 5没有被前面的步骤筛去，因此5是素数，除去所有5的倍数，即10，15；

　　5、 6已经在1中被筛去，因此6不是素数；

　　6、 7没有被前面的步骤筛去，因此7是素数，筛去所有7的倍数，即14；

　　7、8已经在1中被筛去，因此8不是素数；

　　8、9已经在2中被筛去，因此9不是素数；

　　9、10已经在1中被筛去，因此10不是素数；

　　10、11没有被前面的步骤筛去，因此11是素数，筛去所有11的倍数，但是15内没有；

　　11、12已经在1中被筛去，因此12不是素数；

　　12、13没有被前面的步骤筛去，因此13是素数，筛去所有13倍数，但是15内没有；

　　13、14已经在1中被筛去，因此14不是素数；

　　14、15已经在2中被筛去，因此15不是素数；

　　至此，1-15内的所有素数已经全部得到。

 

　　

#include 
     
      #include 
      
       using namespace std;const int SIZE = 1e7;int prime[SIZE];            // 第i个素数bool is_prime[SIZE];    //true表示i是素数 int slove(int n){    int p = 0;    for(int i = 0; i <= n; i++)        is_prime[i] = true;             //初始化    is_prime[0] = is_prime[1] = false;      //0,1不是素数    for(int i = 2; i <= n; i++)    {        if(is_prime[i])                //这里比较巧妙, 我只是意会        {            prime[p++] = i;             //计算素数的个数,也记录下了素数            for(int j = 2 * i; j <= n; j += i)      // 除掉了i的倍数的数字                is_prime[j] = false;        }    }    return p;} int main(){    int n;    while(cin >> n)    {        int res = slove(n);        cout << res << endl;        for(int i = 0; i < res; i++)            cout << prime[i] << endl;    }}