埃氏筛法找寻素数

解题思路:

1.  将2到n范围内的所有整数写下来，即录到数组中（保持数组下标与值一致更加方便解题）；

2.  其中最小的数字2是素数，输出2，并将表中所有2的倍数都划去。

3.  表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数全都划去。

4.  依次类推，如果表中剩余的最小数字是m时，m就是素数（重点！）。然后将表中所有m的倍数全部划去。

5.  像这样反复操作，就能依次枚举n以内的素数。

（示意图：）

注意事项:

参考代码:

#include<iostream>

using namespace std;

int main()

{

  int n;

  cin >> n;                             //寻找范围的上限

  int A[n];                       //n范围之内应该不包含n，所以数组下标上限为n-1

  for (int i = 2; i <n; i++)  //数组赋值

    {

       A[i] = i;                  //直接让下标和值保持一致，i即为A[i]

     }

  for (int i = 2; i <= n; i++)   //遍历数组

    {

       if (A[i] != 0)          //判断不为零时直接输出，并进行后续操作

        {

           cout << i << endl;

           int k = 2;          

           while (k * i<= n)    //i的k倍即为当前A[i]的k倍，令其为零，则不会被输出（这里从2i倍开始，1i倍即为当下A[i]本身，可以不置零，因为它已经被输出）

              {

                   A[k * i] = 0;

                   k++;

              }

        }

     }

return 0;

}