质数筛

Q：给定自然数 n ，求 [1, n] 区间内的所有质数。

1、原始筛法（时间复杂度：O(n√n)）

算法思路：不加思考的暴力枚举，即逐个判断区间内每个数是否是质数。判断单个质数的时间复杂度为O(√n) ，判断 1 ~ n 是否是质数的时间复杂度为O(n√n) 。

代码展示：

int tot, prime[N]; /* prime[i] 为第 i 个质数 */bool is_prime(int n) {    if (n < 2) return false;    for (int i = 2; i * i <= n; i ++)        if (!(n % i))            return false;    return true;}void prime_sieve() {    for (int i = 1; i <= n; i ++)        if (is_prime(i))            prime[++ tot] = i;}

2、普通筛法（时间复杂度：O(n log n)）

算法思路：和原始筛法相比有改进，一个（大于 1）自然数的 k 倍数（k > 1）都一定不是质数。

代码展示：

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数，false 即是 */int tot, prime[N]; /* 共有 tot 个质数，prime[i] 为第 i 个质数 */ void prime_sieve() { 　　for (int i = 2; i <= n; i ++){ 　　　　if (!is_prime[i]) prime[++ tot] = i; 　　　　for (int j = i << 1; j <= n; j += i) 　　　　　　is_prime[j] = true; 　　} }

3、埃氏筛形式 1（时间复杂度：O(n log logn)）

算法思路：著名的质数筛法，由古希腊数学家 Eratosthenes（埃拉托斯特尼）发明，和普通筛法相比减少了许多冗余，一个质数的 k 倍数（k > 1）都一定不是质数。

代码展示：

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数，false 即是 */int tot, prime[N]; /* tot 个质数，prime[i] 为第 i 个质数 */void Eratosthenes_sieve() {    for (int i = 2; i <= n; i ++){        if (!is_prime[i]){            prime[++ tot] = i;            for (int j = i << 1; j <= n; j += i)                 is_prime[j] = true;        }    }}

4、埃氏筛形式 2（时间复杂度：O(n log logn)）

算法思路：埃氏筛的一种不明显的优化，大于 1 的整数的质数倍数不是质数。

代码展示：

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数，false 即是 */int tot, prime[N]; /* 共有 tot 个质数，prime[i] 为第 i 个质数 */ void Eratosthenes_sieve() { 　　for (int i = 2; i <= n; i ++){ 　　　　if (!is_prime[i]) prime[++ tot] = i; 　　　　for (int j = 1; j <= tot && i * prime[j] <= n; j ++) 　　　　　　is_prime[i * prime[j]] = true; 　　} }

5、欧拉筛（时间复杂度：O(n)）

算法思路：最著名、最常用的质数筛！在埃氏筛的形式 2 上多了一行神奇的代码，时间复杂度就从O(nlog logn)降至O(n) ，因其是线性复杂度，所以也称线性筛。如果已经被筛过了，则可以终止这轮筛选合数。

代码展示：

bool is_prime[N]; /* is_prime[i] 表示 i 是不是质数，false 即是 */int tot, prime[N]; /* 共有 tot 个质数，prime[i] 为第 i 个质数 */ void Linear_sieve() { 　　for (int i = 2; i <= n; i ++){ 　　　　if (!is_prime[i]) prime[++ tot] = i; 　　　　for (int j = 1; j <= tot && i * prime[j] <= n; j ++){　　　　　　is_prime[i * prime[j]] = true;                 if (!(i % prime[j])) break; // beautiful !!!           }　　} }

5、埃氏筛形式 1 + bitset（时间复杂度：O(n loglogn)）

算法思路：令人难以置信的是，埃氏筛搭配 C++ 神奇的 bitset 容器（不是 STL），可以让高复杂度的它效率高于低复杂度的欧拉筛！！！

代码展示：

bitset is_prime; /* is_prime[i] 表示 i 是不是质数，true 即是 */int tot, prime[N]; /* tot 个质数，prime[i] 为第 i 个质数 */void Eratosthenes_sieve() {    is_prime.set(); /* 初始化为 true */    is_prime[0] = is_prime[1] = false;    for (int i = 2; i <= n; i ++){        if (!is_prime[i]){            prime[++ tot] = i;            for (int j = i << 1; j <= n; j += i)                 is_prime[j] = false;        }    }}

参考资料：OI Wiki

关键词：