【学习笔记】筛素数

筛素数，是每个人学习编程必须要掌握的东西，我们今天就来分享——各种筛法。
素数：除了1和自身以外，没有其他任何因子的数。

新手级区域：（基础筛~模板筛）
基础筛：

#include <bits/stdc++.h>
using namespace std;

bool def(int x){
    if(x<2){
        return false;
    } // 小于2的数都不是素数。
    for(int i=2;i<x;i++){ // 从2开始遍历到x-1。
        if(x%i==0){
            return false;
        } // 如果有因子就不是素数。
    }
    return true; // 没被筛掉的就是素数。
}

int main() {
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(def(i)==true){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

模板筛：

#include <bits/stdc++.h>
using namespace std;

bool def(int x){
    if(x==2){
        return true; // 2是素数
    }
    if(x<2||x%2==0){
        return false;
    } // 小于2的数 和 除2以外的偶数 都不是素数。
    for(int i=3;i*i<=x;i+=2){ // 从3开始遍历到sqrt(x)。
        if(x%i==0){
            return false;
        } // 如果有因子就不是素数。
    }
    return true; // 没被筛掉的就是素数。
}

int main() {
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(def(i)==true){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

大师级区域：（埃氏筛~欧拉（线性）筛）
埃氏筛：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,cnt=0;
    cin>>n;
    vector<bool>is(n,0);
    for(int i=2;i*i<=n;i++){
        if(!is[i]){
            for(int j=i*2;j<=n;j+=i){
                is[i]=true;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(!is[i]){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

我们还可以让埃氏筛和模板筛结合一下：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,cnt=0;
    cin>>n;
    vector<bool>is(n,0);
    for(int i=3;i*i<=n;i+=2){
        if(!is[i]){
            for(int j=i*i;j<=n;j+=2*i){
                is[i]=true;
            }
        }
    }
    for(int i=3;i<=n;i+=2){
        if(!is[i]){
            cnt++;
        }
    }
    cout<<cnt+(n>1)<<endl;
    return 0;
}

欧拉筛：

#include <cstdio>

const int MAXN = 2000005;
bool is_prime[MAXN];
int primes[MAXN];
int cnt = 0;

int main() {
    int n;
    scanf("%d", &n);
    
    is_prime[0] = true; 
    is_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (!is_prime[i]) {
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
    printf("%d\n", cnt);
}

王者级：（Meissel-Lehmer 算法）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

// 定义数据类型，使用 long long 以支持大数
typedef long long LL;

// --- 预处理配置 ---
// 预处理的范围，通常开到 n^(1/3) 或 n^(1/2) 的某个比例
// 对于 n <= 1e11，开到 5e6 左右比较合适
const int MAXN = 5000000; 

// --- 全局变量 ---
bool is_prime_flag[MAXN];       // 筛法标记数组
int primes[MAXN];               // 存储素数
int pi[MAXN];                   // pi[i] 表示 <= i 的素数个数
int prime_cnt = 0;              // 素数计数器

// --- 1. 线性筛预处理 ---
// 作用：生成小范围素数表，并计算小范围内的 pi(x)
void get_primes() {
    memset(is_prime_flag, true, sizeof(is_prime_flag));
    is_prime_flag[0] = is_prime_flag[1] = false;
    pi[0] = pi[1] = 0;

    for (int i = 2; i < MAXN; ++i) {
        if (is_prime_flag[i]) {
            primes[++prime_cnt] = i;
        }
        pi[i] = prime_cnt; // 记录前缀和

        // 线性筛核心逻辑
        for (int j = 1; j <= prime_cnt && i * primes[j] < MAXN; ++j) {
            is_prime_flag[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

// --- 2. 辅助函数：计算 phi(x, a) ---
// 定义：phi(x, a) 表示在 [1, x] 中，不能被前 a 个素数整除的数的个数
// 这是一个递归函数，配合记忆化（虽然这里主要靠数学性质剪枝）
LL get_phi(LL x, int a) {
    if (a == 0) return x;
    if (x <= 1) return x;
    
    // 优化1：如果 x 很小，直接查表
    if (x < MAXN) return pi[x];

    // 优化2：如果 x < p_a，说明 p_a 无法筛掉任何数，只有 1 是“幸存者”（如果不算1则为0，算1则为1）
    // 但根据定义 phi(x, a) 包含 1，且如果 x < p_a，所有 <=x 的素数都 < p_a
    // 这里使用一个常用的剪枝：如果 x < p_a * p_a，则 phi(x, a) = pi(x) - a + 1
    if (x <= (LL)primes[a] * primes[a]) {
        return pi[x] - a + 1;
    }

    // 递归公式：phi(x, a) = phi(x, a-1) - phi(x/p_a, a-1)
    return get_phi(x, a - 1) - get_phi(x / primes[a], a - 1);
}

// --- 3. 核心函数：Meissel-Lehmer 算法 ---
LL lehmer_pi(LL x) {
    // 基本情况：如果 x 在预处理范围内，直接返回
    if (x < MAXN) return pi[x];

    // 计算关键的边界值
    // a = pi(n^(1/4))  <-- 优化版 Lehmer 常用
    // b = pi(n^(1/2))
    // c = pi(n^(1/3))
    
    // 为了代码简洁且通用，我们采用标准的 Lehmer 分解策略
    // 选取 a = pi(x^(1/3)) 是 Meissel 的原始思路，Lehmer 进行了改进
    // 这里我们选取 a 使得 p_a <= x^(1/3)
    
    LL sqrt_x = (LL)sqrt(x);
    LL cbrt_x = (LL)cbrt(x); // 立方根

    int a = pi[(int)cbrt_x]; // a = pi(x^(1/3))
    int b = pi[(int)sqrt_x]; // b = pi(x^(1/2))

    // 主公式第一部分：phi(x, a) + a - 1
    // 注意：这里实际上是计算 P_1(x) + P_2(x) 的基础部分
    LL result = get_phi(x, a) + a - 1;

    // 主公式第二部分：减去修正项
    // 公式：Sum( pi(x/p_i) - (i-1) ) for i from a+1 to b
    for (int i = a + 1; i <= b; ++i) {
        LL p_i = primes[i];
        // 递归计算 pi(x / p_i)
        // 注意：x/p_i 会迅速变小，很快落入直接查表范围
        result -= lehmer_pi(x / p_i) - (i - 1);
    }

    return result;
}

int main() {
    // 1. 初始化预处理
    get_primes();

    LL n;
    // 2. 循环读取输入 (支持多组测试数据)
    while (scanf("%lld", &n) != EOF) {
        if (n < 2) {
            printf("0\n");
            continue;
        }
        // 3. 计算并输出结果
        printf("%lld\n", lehmer_pi(n));
    }

    return 0;
}

附赠·一整套超级函数库：

#include <cstdio>
#include <cstring>
#include <cstdint>
#include <cstdarg>
#include <immintrin.h>

#pragma GCC optimize("Ofast", "unroll-loops", "no-stack-protector", "fast-math")
#pragma GCC target("avx2", "avx512f", "avx512vl", "fma", "bmi2", "popcnt")
#pragma GCC diagnostic ignored "-Wunused-function"

typedef long long ll;
typedef double lf;

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

#define elif else if

#define swap_d(a, b) do { ll _t = (a); (a) = (b); (b) = _t; } while(0)
#define swap_f(a, b) do { lf _t = (a); (a) = (b); (b) = _t; } while(0)
#define swap_c(a, b) do { char _t = (a); (a) = (b); (b) = _t; } while(0)

#define memcpy(r1, s, len) __builtin_memcpy((r1), (s), (len))
#define strlen(r1) __builtin_strlen((r1))
#define memcmp(s1, s2, n) __builtin_memcmp((s1), (s2), (n))

static const lf pi = 3.14159265358979323846;
static const lf e = 2.71828182845904523536;

static char _rbuf[1 << 16];
static char* _rptr = _rbuf;
static char* _rend = _rbuf;

// 获取下一个字符(带缓冲)
static inline char _gc() {
    if (unlikely(_rptr == _rend)) { // 缓冲区耗尽是小概率事件
        _rend = _rbuf + fread(_rbuf, 1, sizeof(_rbuf), stdin);
        _rptr = _rbuf;
        if (unlikely(_rptr == _rend)) return EOF; // 文件结束是极小概率事件
    }
    return *_rptr++;
}

static char _wbuf[1 << 16];
static char* _wptr = _wbuf;

// 输出单个字符(带缓冲)
static inline void _pc(char c) {
    if (unlikely(_wptr == _wbuf + sizeof(_wbuf))) { // 缓冲区满是小概率事件
        fwrite(_wbuf, 1, sizeof(_wbuf), stdout);
        _wptr = _wbuf;
    }
    *_wptr++ = c;
}

// 刷新输出缓冲区
static inline void _return() {
    if (likely(_wptr != _wbuf)) { // 通常为 True
        fwrite(_wbuf, 1, _wptr - _wbuf, stdout);
        _wptr = _wbuf;
    }
}

namespace std{
    struct string {
    char r1[1001]; 

    // 初始化空字符串
    string() { r1[0] = '\0'; }
    
    // 初始化为单字符
    string(char c) { r1[0] = c; r1[1] = '\0'; }
    
    // 从C字符串构造
    string(const char* s) {
        if (unlikely(!s)) { r1[0] = '\0'; return; }
        size_t len = strlen(s);
        if (len > 1000) len = 1000;
        memcpy(r1, s, len);
        r1[len] = '\0';
    }

    // 拷贝构造函数
    string(const string& other) {
        size_t len = strlen(other.r1);
        if (len > 1000) len = 1000;
        memcpy(r1, other.r1, len);
        r1[len] = '\0';
    }

    // 赋值操作符重载
    string& operator=(const string& other) {
        if (this != &other) {
            size_t len = strlen(other.r1);
            if (len > 1000) len = 1000;
            memcpy(r1, other.r1, len);
            r1[len] = '\0';
        }
        return *this;
    }

    // 下标访问操作符重载(可写)
    inline char& operator[](int i) { return r1[i]; }
    
    // 下标访问操作符重载(只读)
    inline const char& operator[](int i) const { return r1[i]; }

    // 字符串相等判断操作符重载
    bool operator==(const string& other) const {
        size_t l1 = strlen(r1);
        size_t l2 = strlen(other.r1);
        if (l1 != l2) return false;
        return memcmp(r1, other.r1, l1) == 0;
    }
    
    // 字符串不等判断操作符重载
    bool operator!=(const string& other) const { return !(*this == other); }

    // 字符串拼接操作符重载(返回新字符串)
    string operator+(const string& other) const {
        string res;
        size_t l1 = strlen(r1);
        size_t l2 = strlen(other.r1);
        size_t total = l1 + l2;
        if (total > 1000) total = 1000;
        
        if (l1 > 0) memcpy(res.r1, r1, l1);
        if (total > l1 && l2 > 0) {
            size_t copy_len = (total - l1 < l2) ? (total - l1) : l2;
            memcpy(res.r1 + l1, other.r1, copy_len);
        }
        res.r1[total] = '\0';
        return res;
    }

    // 原地拼接字符串操作符重载(string)
    string& operator+=(const string& other) {
        size_t l1 = strlen(r1);
        size_t l2 = strlen(other.r1);
        if (l1 + l2 >= 1000) {
            size_t space = 1000 - l1;
            if (space > 0) memcpy(r1 + l1, other.r1, space);
            r1[1000] = '\0';
        } else {
            memcpy(r1 + l1, other.r1, l2);
            r1[l1 + l2] = '\0';
        }
        return *this;
    }

    // 原地拼接C字符串操作符重载
    string& operator+=(const char* s) {
        size_t l1 = strlen(r1);
        size_t l2 = strlen(s);
        if (l1 + l2 >= 1000) {
            size_t space = 1000 - l1;
            if (space > 0) memcpy(r1 + l1, s, space);
            r1[1000] = '\0';
        } else {
            memcpy(r1 + l1, s, l2);
            r1[l1 + l2] = '\0';
        }
        return *this;
    }

    // 原地拼接字符操作符重载
    string& operator+=(char c) {
        size_t len = strlen(r1);
        if (likely(len < 1000)) {
            r1[len] = c;
            r1[len + 1] = '\0';
        }
        return *this;
    }

    // 获取字符串长度
    inline int size() const { return (int)strlen(r1); }
    
    // 判断字符串是否为空
    inline bool empty() const { return r1[0] == '\0'; }
    
    // 获取C风格字符串指针
    inline const char* c_str() const { return r1; }
    
    // 清空字符串
    inline void clear() { r1[0] = '\0'; }

    // 尾部追加字符
    inline void push_back(char c) {
        size_t len = strlen(r1);
        if (likely(len < 1000)) {
            r1[len] = c;
            r1[len + 1] = '\0';
        }
    }

    // 获取子串
    string substr(int pos, int len = -1) const {
        string res;
        int sz = (int)strlen(r1);
        if (pos < 0) pos = 0;
        if (pos >= sz) return res;
        if (len < 0 || pos + len > sz) len = sz - pos;
        memcpy(res.r1, r1 + pos, (size_t)len);
        res.r1[len] = '\0';
        return res;
    }

    // 查找子串位置
    int find(const string& sub) const {
        if (sub.empty()) return 0;
        const char* p = strstr(r1, sub.r1);
        return p ? (int)(p - r1) : -1;
    }
};

// C字符串 + 自定义字符串
inline string operator+(const char* s, const string& str) {
    string res(s);
    res += str;
    return res;
}

// 字符 + 自定义字符串
inline string operator+(char c, const string& str) {
    string res(c);
    res += str;
    return res;
}

// 字符串快读 (跳过空白)
inline string read_s() {
    string a;
    char c = _gc();
    while (c <= 32) {
        if (c == EOF) return a;
        c = _gc();
    }
    int cnt = 0;
    while (c > 32 && cnt < 1000) {
        a.r1[cnt++] = c;
        c = _gc();
    }
    a.r1[cnt] = '\0';
    return a;
}

// 读取整行 (不含换行符)
inline void getline(string& s) {
    char c = _gc();
    int cnt = 0;
    while (cnt < 1000) {
        if (c == '\n' || c == '\r' || c == EOF) break;
        s.r1[cnt++] = c;
        c = _gc();
    }
    s.r1[cnt] = '\0';
}

// 字符串快写
inline void write_s(const string& a) {
    const char* p = a.r1;
    while (*p) _pc(*p++);
}

// 字符串反转
inline void reverse(string& s) {
    int len = s.size();
    int half = len >> 1;
    char* start = s.r1;
    char* end = s.r1 + len - 1;
    for (int i = 0; i < half; ++i) {
        swap_c(*start, *end);
        start++;
        end--;
    }
}
    
}; // string 类型 字符串（带输出输入工具）
using namespace std;

namespace Code{
    // 整数快读 (ll)
inline ll read_d() {
    ll x = 0;
    int f = 1;
    char c = _gc();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = _gc();
        if (unlikely(c == EOF)) break;
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48); 
        c = _gc();
    }
    return f == 1 ? x : -x;
}

// 浮点快读 (lf)
inline lf read_f() {
    ll ip = 0;
    lf f = 1.00;
    char c = _gc();
    
    // 1. 跳过前导空白和符号
    while (c < '0' || c > '9') {
        if (c == '-') f = -1.00;
        c = _gc();
        if (unlikely(c == EOF)) break;
    }
    
    // 2. 读取整数部分
    while (c >= '0' && c <= '9') {
        ip = (ip << 3) + (ip << 1) + (c ^ 48); 
        c = _gc(); // 此时 c 已经是小数点或者分隔符（如空格）
    }
    
    lf fp = 0.00, base = 0.1;
    
    // 3. 直接使用刚才读到的 c 进行判断，不要重新 _gc()
    if (c == '.') {
        c = _gc(); // 只有确认是小数点后，才读取下一位小数
        while (c >= '0' && c <= '9') {
            fp += (c ^ 48) * base;
            base *= 0.1;
            c = _gc();
        }
    }
    
    return double(ip + fp) * f;
}

inline void read_w(const char* fmt, ...) {
        va_list args;
        va_start(args, fmt);
        
        char c;
        while (*fmt) {
            if (*fmt == '%') {
                fmt++;
                if (!*fmt) break;

                if (*fmt == 's') {
                    string* s = va_arg(args, string*);
                    s -> clear();
                    c = _gc();
                    while (c <= 32) { if (c == EOF) goto end; c = _gc(); }
                    while (c > 32) {
                        s->push_back(c);
                        c = _gc();
                        if(c == EOF) break;
                    }
                }
                else if (*fmt == 'd') {
                    ll* val = va_arg(args, ll*);
                    *val = read_d();
                }
                else if (*fmt == 'c') {
                    char* val = va_arg(args, char*);
                    *val = _gc();
                }
                else if (*fmt == 'l') {
                    if (*(fmt+1) == 'f') {
                        fmt++;
                        lf* val = va_arg(args, lf*);
                        *val = read_f();
                    }
                }
                else if (*fmt == 'f') {
                     lf temp = read_f();
                     float* val = va_arg(args, float*);
                     *val = (float)temp;
                }
            } else {
                c = _gc();
                while (c <= 32 && *fmt != '%') c = _gc();
            }
            fmt++;
        }
        end:
        va_end(args);
    }

// 整数快写 (ll)
void write_d(ll x) {
    if (x == 0) { _pc('0'); return; }
    if (x < 0) { _pc('-'); x = -x; }
    char buf[25]; 
    char* ptr = buf + 24;
    *ptr = '\0';
    while (x > 0) {
        *--ptr = '0' + (char)(x % 10);
        x /= 10;
    }
    while (*ptr) _pc(*ptr++);
}

// 浮点快写 (指定位数)
inline void write_p(lf x, int max_decimal) {
    if (x == 0.0) { _pc('0'); return; }
    if (x < 0) { _pc('-'); x = -x; }
    
    ll int_part = (ll)x;
    write_d(int_part);
    
    if (max_decimal <= 0) return;
    _pc('.');
    
    lf frac_part = x - (lf)int_part;
    for (int i = 0; i < max_decimal; i++) {
        frac_part *= 10.0;
        ll digit = (ll)frac_part;
        _pc('0' + (char)digit);
        frac_part -= (lf)digit;
    }
}

// 浮点快写 (默认15位精度)
inline void write_f(lf x) { write_p(x, 15); }

// 格式化输出 (类似printf)
void write_w(const char* fmt, ...) {
    va_list args;
    va_start(args, fmt);
    
    while (*fmt) {
        if (*fmt == '%') {
            fmt++; 
            if (!*fmt) break;
            
            ll precision = -1;
            if (*fmt == '.' && *(fmt+1) == '*') {
                fmt += 2;
                precision = va_arg(args, ll);
            } 
            else if (*fmt == '.') {
                fmt++;
                ll p = 0;
                bool has_digit = false;
                while(*fmt >= '0' && *fmt <= '9') {
                    p = p * 10 + (*fmt - '0');
                    fmt++;
                    has_digit = true;
                }
                if (has_digit) precision = p;
            }

            switch (*fmt) {
                case 'd':
                case 'i':
                    write_d((ll)va_arg(args, ll));
                    break;
                case 'l':
                    if (*(fmt+1) == 'd') {
                        write_d(va_arg(args, ll));
                        fmt++;
                    } else {
                        write_d((ll)va_arg(args, ll));
                    }
                    break;
                case 'L':
                     if (*(fmt+1) == 'd') {
                        write_d(va_arg(args, ll));
                        fmt++;
                     }
                     break;
                case 'f':
                case 'F':
                case 'g':
                case 'G':
                    if (precision >= 0) {
                        write_p(va_arg(args, lf), precision);
                    } else {
                        write_f(va_arg(args, lf));
                    }
                    break;
                case 's': {
                    const char* s = va_arg(args, const char*);
                    write_s(s);
                    break;
                }
                case 'c':
                    _pc((char)va_arg(args, int));
                    break;
                case '%':
                    _pc('%');
                    break;
                default:
                    _pc('%');
                    _pc(*fmt);
                    break;
            }
        } else if (*fmt == '\\') {
            fmt++;
            if (!*fmt) break;
            switch (*fmt) {
                case 'n': _pc('\n'); break;
                case 't': _pc('\t'); break;
                case 'r': _pc('\r'); break;
                case '\\': _pc('\\'); break;
                case '"': _pc('"'); break;
                default: 
                    _pc('\\'); 
                    _pc(*fmt); 
                    break;
            }
        } else {
            _pc(*fmt);
        }
        fmt++;
    }
    
    va_end(args);
}
};
using namespace Code; // C语言输出输入工具

namespace math{
    // 整数数组求和
ll sum_d(ll a[], int n) {
    ll sum = 0;
    for (int i = 0; i < n; ++i) sum += a[i];
    return sum;
}

// 浮点数组求和
lf sum_f(lf a[], int n) {
    lf sum = 0;
    for (int i = 0; i < n; ++i) sum += a[i];
    return sum;
}

// 浮点乘方 (优化)
lf pow(lf a, lf b) {
    ll ll_b = (ll)b;
    lf lf_b = b - ll_b;
    if (lf_b != 0.00) return __builtin_pow(a, b);
    
    if (a == 1.0 || ll_b == 0) return 1.0;
    if (a == 0.0) return 0.0;
    if (a == -1.0) return (ll_b & 1) ? -1.0 : 1.0;

    bool neg = false;
    if (ll_b < 0) {
        neg = true;
        ll_b = -ll_b;
    }

    lf res = 1.0;
    lf base = a;
    while (ll_b > 0) {
        if (ll_b & 1) res *= base;
        base *= base;
        ll_b >>= 1;
    }
    return neg ? 1.0 / res : res;
}

lf sqrt(lf x, lf n) {if (unlikely(n == 0 || x == 0)) return 0;
    if (unlikely(n == 1)) return x;
    if (likely(n == 2)) return __builtin_sqrt(x);
    if (unlikely(x < 0 && static_cast<long long>(n) % 2 == 0)) { 
        return 0.0L / 0.0L;
    }

    // 3. 牛顿迭代法
    long double y = x; // 初始猜测值，可以设为 x 或 1.0
    long double prev_y;
    const long double epsilon = 1e-15L; // 精度控制，当两次迭代结果差值小于此值时停止

    do {
        prev_y = y;
        long double y_power_n_minus_1 = 1.0L;
        for (int i = 0; i < static_cast<int>(n) - 1; ++i) {
            y_power_n_minus_1 *= prev_y;
        }
        y = ((n - 1) * prev_y + x / y_power_n_minus_1) / n;
        
    } while (y > prev_y ? y - prev_y > epsilon : prev_y - y > epsilon);

    return y;
}

// 最大公约数
inline ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap_d(a, b);
    }
    return a;
}

// 最小公倍数
inline ll lcm(ll a, ll b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}
}; // 数学函数库
using namespace math;

// 自定义区域

// 主函数入口
int main() {
    _return();
}

都看到这里了，点个赞吧，求求了！！！