一、筛法：

1.埃式筛法：

介绍：最简便的筛法，对素数的倍数进行筛选。

在埃式筛法中代码复杂度为O（n*loglogn），可看出合数可由多个质因子数筛去，如果只由最小质因子除去，那可大大简化复杂度。

#include <iostream>
#include <cstring>

using namespace std;

bool u[10005]; // 筛子

int main(){
    int n;
    n = 10000;
    memset(u,true,sizeof(u));  //初始化
    for (int i = 2; i <= n; i++){  // 顺序搜索
        if (u[i]){
            for (int j = 2; i*j <= n;j ++){  //将素数的倍数筛去
                u[i*j] = false;
            }
        }
    }
    int su[10005];
    int num = 0;
    for (int i = 2;i <= n;i++){  // 将筛中保留的数存入su[]中
        if (u[i]){
            su[num++] = i;
        }
    }
    for (int i = 0;i < num; i++){
        cout<<su[i]<<endl;
    }
    return 0;
}

2.欧拉筛法

介绍：合数仅有它的最小素因子筛去，复杂度可优化至O（n）

最难理解的地方是 i % su[ j ] == 0,其作用是保证合数都被他的最小素因子筛去。

当 i % su[ j ] == 0 可写为 i = m * su[ j ] (m 为i / su[ j ] ) 。若不跳出，择下一个方程为

i * su[ j +1 ] => m * su[ j+1 ] * su[j] ，可得出 i *su[ j +1 ] 也是su [ j ]的倍数，
su [ j +2 ] 之后也是如此。

#include <iostream>
#include <cstring>

using namespace std;

bool u[10005]; // 筛子
int su[10005]; // 保留的素数

int main(){
    int n;
    n = 10000;
    int num = 1;
    memset(u,true,sizeof(u));  //初始化
    for (int i = 2; i <= n; i ++){
        if (u[i]) su[num++] = i;  //为素数存入
        for (int j = 1;j < num;j ++){
            if (i * su[j] > n) break;  //超出n的范围，计算下一个整数
            u[i * su[j]] = false; // 消除 i * 素数 的积
            if (i % su[j] == 0) break; //当前素数为i的最小素因子，直接break计算下一个。
        }
    }
    for (int i = 1; i < num; i++){  //输出素数
        cout<<su[i]<<endl;
    }
    return 0;
}