is_prime函数通过特判n
怎么用 is_prime 快速判断单个数是否为素数
对单个整数做素性判断，最直接的方式是试除法：检查从 2 到 √n 是否有能整除 n 的数。但要注意几个关键点：
- 必须特判
n （<code>0、1不是素数），n == 2直接返回 true - 偶数只需检查
n == 2，其余偶数直接返回 false，避免一半无谓循环 - 循环起点设为 3，步长为 2，只试奇数因子
- 上界用
i * i 而非 <code>i ，避免浮点误差和 <code>sqrt调用开销
bool is_prime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}筛到 10⁶ 以内用 std::vector<bool></bool> 做埃氏筛就够了
当需要批量判断 [2, N] 内所有数是否为素数，埃拉托斯特尼筛法（埃氏筛）简单可靠。对 N ≤ 10⁶，用 std::vector<bool></bool> 即可，空间紧凑且缓存友好：
- 初始化全为
true，is_prime[0]和is_prime[1]设为false - 外层循环只需到 √N；内层从
i * i开始标记，因为更小的倍数已被更小的质数筛过 - 避免使用
vector<int></int>或bitset（除非 N > 10⁷），前者浪费空间，后者在小规模下无明显优势且语法冗余
std::vector<bool> sieve(int n) {
std::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;
}
}
}
return is_prime;
}筛到 10⁷ 以上建议改用线性筛（欧拉筛）
埃氏筛时间复杂度是 O(N log log N)，而线性筛能做到严格 O(N)，关键在于每个合数只被其最小质因子筛一次。它适合 N ≥ 10⁷ 且内存允许的情况：
- 维护一个质数列表
primes和一个最小质因子数组min_prime（或仅用is_prime+ 额外逻辑） - 内层循环中，一旦发现
i % primes[j] == 0，立刻 break —— 这保证了后续更大的质数不会用来筛i * primes[j]，否则最小质因子就不是primes[j] - 注意数组大小要开到 N+1，且
primes容量预留足够（π(N) ≈ N / ln N）
std::vector<int> linear_sieve(int n) {
std::vector<bool> is_prime(n + 1, true);
std::vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) primes.push_back(i);
for (int p : primes) {
if (i * p > n) break;
is_prime[i * p] = false;
if (i % p == 0) break;
}
}
return primes;
}别在运行时反复调用 is_prime 判断大量数字
如果问题本质是「查询多个数是否为素数」，比如输入 10⁵ 个数分别判断，哪怕单次 is_prime 是 O(√n)，最坏情况可能超时（例如全为 10⁹ 附近的大数）。这时应：
立即学习“C++免费学习笔记（深入）”；
- 先收集所有待查数，取最大值
max_n - 若
max_n ≤ 10⁶，直接筛出[2, max_n]的素数表，O(1) 查询 - 若
max_n > 10⁶但查询数不多（如 ≤ 10⁴），仍可用优化版is_prime，但务必加 6k±1 优化（跳过所有 2、3 的倍数） - 注意：6k±1 优化需额外特判 2 和 3，且循环步长变成 6，起始点为 5 和 7
很多人卡在“以为单次试除够快”，实际数据一多，缓存不友好 + 重复开方 + 偶数未剪枝，性能会断崖式下跌。
