有两种筛法，第一种叫做埃拉托斯特尼筛法（复杂度O(n log logn)），另一种是欧拉筛法（复杂度O(n)）

埃拉托斯特尼筛法其实就是用已得到质数，去将他的所有n以内倍数标记为合数，最后剩下的就是合数。

在进行筛法的同时，可以顺便找到每个数的最小质因数（就是第一次更新他的那个质数）

 

欧拉筛法：在埃氏筛法中每一个合数可能会被更新很多遍，这些是没有必要的，所以就有了欧拉筛。

欧拉筛的思路就是保证每个合数只被他的最小质因数筛掉。用一个数组dis来存已经得到的素数，

然后再用已经得到素数取筛其他的数，主要的地方是代码中  if(i%dis[j]==0) break;  这个地方。

两个筛法的代码

 1 #include<cstdio>
 2 #include<iostream>
 3  using namespace std;
 4   const int N=10000;
 5   void aa(int n);
 6   void ol(int n);
 7   int main()
 8   {
 9      int n;
10      scanf("%d",&n);
11      aa(n);
12      printf("\n");
13      ol(n);
14  }
15  
16  void aa(int n)//埃氏筛法 
17  {
18      int vis[N];
19      int dis[N];//用来存最小质因数 
20      for(int i=2;i<=n;++i)
21      {
22          if(!vis[i])
23          {
24              for(int j=i*2;j<=n;j+=i)
25              {
26                  if(!vis[j])
27                  {
28                      vis[j]=1;
29                      dis[j]=i;
30                  }
31              }
32          }
33      }
34      for(int i=1;i<=n;++i)
35      {
36          if(!vis[i])
37          {
38              printf("%d ",i);
39          }
40      }
41  }
42  void ol(int n)
43  {
44      int vis[N];
45      int dis[N],js=0;
46      for(int i=2;i<=n;++i)
47      {
48          if(!vis[i])
49          {
50              dis[++js]=i;
51          }
52          for(int j=1;dis[j]*i<=n;++j)
53          {
54              vis[i*dis[j]]=1;
55              if(i%dis[j]==0) break;
56          }
57      }
58      for(int i=1;i<=n;++i)
59      {
60          if(!vis[i]) printf("%d ",i);
61      }
62  }