质数筛

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 log n)）

算法思路：著名的质数筛法，由古希腊数学家 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 log n)）

算法思路：埃氏筛的一种不明显的优化，大于 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(n log log n) 降至 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 log log n)）

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

代码展示：

bitset<N> 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