埃氏筛配合std::vector预处理10⁶内素数最实用，兼顾简洁性、可读性与性能；单个大数素性判断用Miller-Rabin（配7个确定性底数）；查素数表优先用std::lower_bound。
用 std::vector + 埃氏筛预处理 10⁶ 以内素数最实用
绝大多数 C++ 实际场景（比如 OJ 题、算法预处理、小范围质数枚举）不需要实时判断单个大数是否为素数，而是要快速获取一段连续范围内的所有素数。这时候埃拉托斯特尼筛法（埃氏筛）配合 std::vector<bool></bool> 是平衡简洁性、可读性和性能的首选。
常见错误是手写 is_prime(int n) 对每个数试除——10⁵ 个查询就可能超时；或者用 vector<int></int> 存筛出的素数但忘了初始化大小，导致反复 push_back 引发内存重分配开销。
实操建议：
- 筛前先
vector<bool> is_prime(n + 1, true)</bool>，注意索引 0 和 1 要设为false - 外层循环只需到
sqrt(n)，且从i * i开始标记（i * 2可能已被更小的素数筛过） - 如果只要素数列表，最后遍历一次
is_prime收集下标即可，别边筛边存——缓存不友好 -
vector<bool></bool>是特化类型，空间省但访问略慢；若对性能极端敏感且内存充足，可用vector<char></char>
int n = 1000000;
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
判断单个大数是否为素数：用 Miller-Rabin 比试除快得多
当输入是单个 64 位整数（比如 long long），且值可能接近 10¹⁸ 时，试除法最多要跑 √n ≈ 10⁹ 次，肯定超时。Miller-Rabin 是概率性算法，但对 64 位整数，用固定底数集（如 {2, 325, 9375, 28178, 450775, 9780504, 1795265022}）可做到确定性正确。
立即学习“C++免费学习笔记（深入）”；
容易踩的坑：
- 快速幂中乘法溢出：必须用
__int128（GCC）或自写模乘，不能直接(a * b) % mod - 把
n == 2或n < 2的边界漏掉，导致对 1、2、偶数处理出错 - 误以为“通过一轮测试 = 是素数”，其实需对多个底数测试；不过对 uint64_t，上述 7 个底数已覆盖全部
使用场景：密码学参数生成、大数分解前置判断、交互题中动态质数验证。
std::lower_bound 查素数表比线性扫快得多
如果你已经用埃氏筛生成了 vector<int> primes</int>（升序），后续要频繁查“≤x 的最大素数”或“第 k 小素数”，千万别用 for 循环遍历——O(n) 太慢。
实操建议：
- 查第一个 ≥ x 的素数位置：用
lower_bound(primes.begin(), primes.end(), x) - 查最后一个 ≤ x 的素数：用
upper_bound然后减一，注意判越界 - 确保
primes是全局或静态构造，避免重复筛；C++17 可用inline constexpr vector（需编译器支持） - 若只查几十次，预处理成本可能得不偿失；但查上百次，O(log π(n)) ≈ O(log n) 就明显占优
Windows 下 clang++ 编译 Miller-Rabin 可能缺 __int128
Clang for Windows（尤其 MinGW-w64 工具链）默认不启用 __int128，而 Miller-Rabin 的模乘又极度依赖它。此时会编译报错：error: use of undeclared identifier '__int128'，或运行时乘法溢出导致误判。
解决办法很具体：
- 加编译选项
-D__SIZEOF_INT128__强制定义（仅限 GCC/Clang 兼容环境） - 改用三模乘（
mulmod(a, b, m)分三段模拟），但代码变长、常数变大 - 换用 MSVC？不行，它原生不支持
__int128，且无对应内置函数 - 最稳方案：Linux/macOS 下开发，或用 WSL；生产环境部署也建议避开 Windows 原生 Clang 做大数素性检测
这个点非常容易被忽略——算法逻辑全对，只因平台差异，is_prime(1000000000000000000LL) 返回 false。
