素数筛法

板子题网址1: https://www.luogu.com.cn/problem/P3383

板子题网址2: https://www.luogu.com.cn/problem/P3912

速度比欧拉筛还快的埃氏筛

const int N = 1e8 + 5;
int prime_cnt = 0;
int primes[N >> 3];
bitset<N> is_prime;

inline void get_prime(int n) {
    is_prime.set();
    for (int i = 3; i * i < n; i += 2)
        if (is_prime[i])
            for (int j = i * i; j < n; j += 2 * i)
                is_prime[j] = false;
    primes[prime_cnt++] = 2;
    for (int i = 3; i < n; i += 2)
        if (is_prime[i]) primes[prime_cnt++] = i;
}

速度测试

以下代码均使用 g++-4.8 code.cpp -O2 命令行编译，CPU 使用 Intel i5-8259U 进行测试。测试结果取十次平均值。

从测试结果中可知，时间复杂度 $O(n \log \log n)$ 的埃氏筛在使用 bitset 优化后速度甚至超过时间复杂度 O(n) 的欧拉筛，而欧拉筛在使用 bitset 后会出现「负优化」的情况。