问题引入

给定整数N(1<N<100000)，输出所有素数.

本题可以用暴力求解,但是显然在竞赛中是不可取的，因为复杂度接近O(n^2)
从另一角度思考，素数的倍数一定不是素数。可以先将数据存储在一个数组中，标定0为素数，1为非素数。数组从2开始遍历，如果n[i]=0，则将所有n[i]的倍数都标记为1，以此类推。最后为0的便是素数。
代码如下

/*用筛选法求100000以内的所有素数*/
#include<stdio.h>
int main()
{
  int n[100001] = {0};
  int i,j;
  for(i=2;i<=100000;i++)
  {
    if(n[i] == 0)
    {
      for(j=i*2;j<=100000;j+=i)
      {
        n[j] = 1;
      }
    }
  }
  for(i=2;i<=100000;i++)
  {
    if(n[i] == 0) printf("%d\n",i);
  }
}

这样复杂度会大大降低，但是还有可以优化的地方。

/*用筛选法求100000以内的所有素数*/
#include<stdio.h>
#include<math.h>
int main()
{
    int n[100001] = {0};
    int i,j;
    for(i=2;i<=(int)sqrt(100000);i++)  
    {
        if(n[i] == 0)
        {
            for(j=i*i;j<=100000;j+=i)
            {
                n[j] = 1;
            }
        }
    }
    for(i=2;i<=100000;i++)
    {
        if(n[i] == 0) printf("%d\n",i);
    }
}

这样复杂度更低了。

当题目要求求很多组数据，则可以在第一次将所有结果保存在一个数组中，这样就免去了每一组数据求一次解的步骤。这便是预处理。