　　求质数表是一道常见的编程入门题目，也是一道经典的码农面试题。很多人都学过「试除法」和「筛法」两种方法。不过你可曾想过，这两种基本方法里，还有多少水分可以挤呢？

　　我在寒假中研究了 9 种求质数表的算法，想用知乎 live 的形式与大家分享。由于一口吃不成胖子，我会分两次介绍全部 9 种算法。所有算法均用 C 语言实现。

　　在第一次 live 中，我会首先讲解两种基本算法：试除法和埃氏筛法。它们的时间复杂度都高于线性；我还会讲解两种时间复杂度等于线性的筛法：欧拉筛与简易欧拉筛。

　　在第二次 live 中，我会讲解如下几种高级算法：

增量式筛法：无需事先指定范围，可以不停地寻找质数；
分段式筛法：把空间复杂度从 O(N) 降至 O(sqrt(N))；
轮式筛法：降低时间复杂度。它可以与前面的任意算法复合，我会讲轮式埃氏筛、轮式简易欧拉筛、轮式分段埃氏筛三个例子，其中轮式简易欧拉筛把时间复杂度降至O(N)以下。

　　第一次 live 的难度不高，有编程基础的听众都可以参加；第二次 live 的难度较高，大家可以在听过第一次之后再决定是否参加。我会把 PPT 上传到 live 中，以便复习。

　　两次 live 的开始时间如下：

第一次 live 预计持续 1 小时，第二次 live 预计持续 1 ~ 1.5 小时。

　　Live 地址：

ITPub博客

10898 求质数表的n种境界——知乎Live预告