企业官网建设流程全解析

网站标题的写法,平坝网站建设,手工制作书签简单又好看,网站建设的论坛目录 ​编辑 前言 一、质数的定义与直观判定 1.1 质数与合数的概念 1.2 试除法的优化#xff1a;从 O (n) 到 O (√n) 1.3 C 实现质数判定函数 1.4 实战例题#xff1a;洛谷 P5736 质数筛 二、筛法入门#xff1a;埃氏筛法#xff08;Eratosthenes Sieve#xff0…目录​编辑前言一、质数的定义与直观判定1.1 质数与合数的概念1.2 试除法的优化从 O (n) 到 O (√n)1.3 C 实现质数判定函数1.4 实战例题洛谷 P5736 质数筛二、筛法入门埃氏筛法Eratosthenes Sieve2.1 筛法的核心思想2.2 埃氏筛法的基本实现2.3 C 实现埃氏筛法2.4 埃氏筛法的时间复杂度与优化2.5 实战例题洛谷 P3383 模板线性筛素数三、筛法巅峰线性筛法欧拉筛法3.1 埃氏筛法的局限性3.2 线性筛法的核心原理3.3 线性筛法的逻辑拆解3.4 C 实现线性筛法3.5 线性筛法的优势与应用场景四、进阶实战质数相关经典例题解析4.1 例题 1洛谷 P1835 素数密度4.2 例题 2UVA543 Goldbachs Conjecture五、质数相关算法的常见误区与优化技巧5.1 常见误区5.2 优化技巧总结前言在算法竞赛的数论板块中质数相关问题始终是高频考点。无论是判断单个数字是否为质数还是快速筛选出一定范围内的所有质数这些基础技能不仅是解决复杂数论问题的基石更是拉开竞赛分数差距的关键。本文将从质数的定义出发深入剖析质数判定的优化思路详解埃氏筛法与线性筛法的原理与实现带大家彻底掌握这部分核心内容。下面就让我们正式开始吧一、质数的定义与直观判定1.1 质数与合数的概念质数又称素数是指大于 1 的自然数中除了 1 和它本身以外不再有其他因数的数。与之相对的是合数合数是指大于 1 且不是质数的自然数。特别规定1 既不是质数也不是合数。这个定义看似简单但在实际判定时却藏着不少优化空间。比如判断一个数 x 是否为质数最直观的思路是检查从 2 到 x-1 的所有整数是否能整除 x。但这样的暴力解法效率极低当 x 达到 1e5 甚至更大时必然会超时。1.2 试除法的优化从 O (n) 到 O (√n)我们可以通过一个关键性质优化判定过程如果 a 是 x 的约数那么 x/a 也一定是 x 的约数。这意味着我们无需检查到 x-1只需检查到√x 即可。因为如果 x 存在大于√x 的因数那么它对应的另一个因数必然小于√x在此之前就已经被检查过了。举个例子判断 100 是否为质数√10010我们只需检查 2 到 10 之间的数。发现 2 能整除 100直接判定 100 为合数无需继续检查后续数字。此外在代码实现时为了避免使用 sqrt 函数带来的精度问题我们可以采用i x / i的写法既保证了逻辑正确性又提升了代码效率。1.3 C 实现质数判定函数bool isprime(int x) { if (x 1) return false; // 小于等于1的数直接排除 // 试除法核心枚举到√x即可 for (int i 2; i x / i; i) { if (x % i 0) return false; // 存在其他因数不是质数 } return true; // 未找到其他因数是质数 }这个函数的时间复杂度为O (√x)对于 1e9 以内的单个数字判定完全足够。比如判断 1e97 是否为质数只需循环约 3e4 次效率极高。1.4 实战例题洛谷 P5736 质数筛题目链接https://www.luogu.com.cn/problem/P5736题目描述输入 n 个不大于 1e5 的正整数去除掉不是质数的数字依次输出剩余的质数。解题思路对于每个输入的数字调用上述 isprime 函数进行判定将判定为质数的数字输出即可。C 参考代码#include iostream using namespace std; bool isprime(int x) { if (x 1) return false; for (int i 2; i x / i; i) { if (x % i 0) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) { int x; cin x; if (isprime(x)) { cout x ; } } cout endl; return 0; }代码优化说明使用ios::sync_with_stdio(false);和cin.tie(nullptr);关闭输入输出同步提升大数据量下的读取速度避免因输入输出耗时导致超时。二、筛法入门埃氏筛法Eratosthenes Sieve2.1 筛法的核心思想当需要找出 [1, n] 范围内的所有质数时逐个判定的方法效率较低时间复杂度 O (n√n)。筛法的核心思想是 “标记非质数”利用质数的倍数一定是合数的性质从 2 开始将每个质数的所有倍数标记为合数未被标记的数即为质数。2.2 埃氏筛法的基本实现初始化一个布尔数组 stst [i]表示数字 i 是否被标记为合数初始值均为 false。从 2 开始遍历到 n如果 st [i] 为 false说明 i 是质数将其记录下来。然后将 i 的所有倍数从 ii 开始而非 2i标记为 true。这里从 ii 开始是因为小于 ii 的倍数已经被更小的质数标记过了比如 i5 时5210 已被 2 标记5315 已被 3 标记只需从 5*525 开始标记。2.3 C 实现埃氏筛法const int MAXN 1e6 10; bool st[MAXN]; // 标记是否为合数 int primes[MAXN], cnt; // 存储质数cnt为质数个数 void eratosthenes_sieve(int n) { memset(st, false, sizeof st); cnt 0; for (int i 2; i n; i) { if (!st[i]) { // i是质数 primes[cnt] i; // 从i*i开始标记倍数 for (long long j 1LL * i * i; j n; j i) { st[j] true; } } } }2.4 埃氏筛法的时间复杂度与优化埃氏筛法的时间复杂度为O (n log log n)这个复杂度非常接近线性对于 n1e6 的范围几乎可以瞬间完成筛选。关键优化点使用long long类型的 j 避免溢出当 i 接近√n 时ii 可能超过 int 的范围比如 i1e5 时ii1e10超过 int 的最大值 2e9因此需要用 1LL 强制转换为长整型。数组初始化优化使用memset函数快速初始化数组效率大大高于循环赋值。2.5 实战例题洛谷 P3383 模板线性筛素数题目链接https://www.luogu.com.cn/problem/P3383题目描述给定范围 n 和 q 个询问每次输出第 k 小的素数。解题思路先用埃氏筛法筛选出 [1, n] 范围内的所有质数存储在 primes 数组中然后直接响应每个询问。C 参考代码#include iostream #include cstring using namespace std; const int MAXN 1e8 10; // 根据题目n的范围调整 bool st[MAXN]; int primes[MAXN], cnt; void eratosthenes_sieve(int n) { memset(st, false, sizeof st); cnt 0; for (int i 2; i n; i) { if (!st[i]) { primes[cnt] i; for (long long j 1LL * i * i; j n; j i) { st[j] true; } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; eratosthenes_sieve(n); while (q--) { int k; cin k; cout primes[k] endl; } return 0; }注意事项当 n 的范围较大如 1e8时需要注意数组的内存占用。bool 类型数组每个元素占 1 字节1e810 的数组约占 100MB在竞赛允许的内存范围内。三、筛法巅峰线性筛法欧拉筛法3.1 埃氏筛法的局限性埃氏筛法虽然高效但存在一个问题某些合数会被多个质数重复标记。比如 12会被 2 标记一次又会被 3 标记一次。这虽然不影响最终结果但造成了不必要的计算开销。线性筛法又称欧拉筛法的核心创新点是让每个合数只被其最小质因数标记一次从而实现 O (n) 的线性时间复杂度是竞赛中筛选质数的最优方法。3.2 线性筛法的核心原理同样使用 st 数组标记合数primes 数组存储已找到的质数。遍历每个数 i从 2 到 n如果 i 未被标记说明 i 是质数将其加入 primes 数组。遍历 primes 数组中的每个质数p [j]计算ip [j]如果ip [j] n则跳出循环。将i*p [j]标记为合数。关键步骤如果 i 能被 p [j] 整除立即跳出循环。因为此时 p [j] 是 i 的最小质因数也是 ip [j] 的最小质因数如果继续遍历更大的质数就会导致 ip [j] 被更大的质因数标记违背 “只被最小质因数标记” 的原则。3.3 线性筛法的逻辑拆解我们以 i6 为例详细拆解线性筛法的执行过程primes 数组中已有 [2, 3, 5]。遍历 p [j]26*212标记 12 为合数由于 6%20立即跳出循环。这里 12 的最小质因数是 2因此只被 2 标记一次不会再被 3 标记6*31818 会在 i9 时被 3 标记。再以 i5质数为例遍历 p [j]25*210标记 10最小质因数 2。p [j]35*315标记 15最小质因数 3。p [j]55*525标记 25最小质因数 5。p [j]75*735n假设 n30跳出循环。通过这种方式每个合数都只被其最小质因数标记一次确保了线性时间复杂度。3.4 C 实现线性筛法const int MAXN 1e7 10; bool st[MAXN]; int primes[MAXN], cnt; void euler_sieve(int n) { memset(st, false, sizeof st); cnt 0; for (int i 2; i n; i) { if (!st[i]) { // i是质数 primes[cnt] i; } // 遍历所有已找到的质数标记i*primes[j]为合数 for (int j 1; 1LL * i * primes[j] n; j) { st[i * primes[j]] true; if (i % primes[j] 0) { // primes[j]是i的最小质因数 break; } } } }3.5 线性筛法的优势与应用场景线性筛法的时间复杂度严格为O (n)在 n1e7 的范围内其速度远快于埃氏筛法。更重要的是线性筛法在筛选质数的同时还能方便地求出每个数的最小质因数这为后续的质因数分解、欧拉函数计算等操作提供了极大便利。四、进阶实战质数相关经典例题解析4.1 例题 1洛谷 P1835 素数密度题目链接https://www.luogu.com.cn/problem/P1835题目描述给定 L 和 R计算区间 [L, R] 中素数的个数1≤L≤R2^31R-L≤1e6。难点分析R 的范围最大为 2^31-1直接筛选 [1, R] 范围内的质数会导致数组过大需要 2^31 字节约 2GB内存无法承受。解题思路利用 “区间筛法”核心思想是对于区间 [L, R] 中的数其质因数一定不大于√R。因此先筛选出 [1, √R] 范围内的所有质数。用这些质数去标记 [L, R] 范围内的倍数未被标记的数即为质数。C 参考代码#include iostream #include cstring #include cmath using namespace std; typedef long long LL; const int MAXN 1e6 10; bool st_prime[MAXN]; // 标记[1, sqrt(R)]的质数 bool st_range[MAXN]; // 标记[L, R]的合数 int primes[MAXN], cnt; // 筛选[1, n]的质数 void sieve(LL n) { memset(st_prime, false, sizeof st_prime); cnt 0; for (LL i 2; i n; i) { if (!st_prime[i]) { primes[cnt] i; for (LL j i * i; j n; j i) { st_prime[j] true; } } } } int count_primes(LL L, LL R) { memset(st_range, false, sizeof st_range); // 用[1, sqrt(R)]的质数标记[L, R]的倍数 for (int i 1; i cnt; i) { LL p primes[i]; // 计算区间[L, R]中p的最小倍数max(p*2, ceil(L/p)*p) LL start max(2LL * p, (L p - 1) / p * p); for (LL j start; j R; j p) { st_range[j - L] true; // 映射到数组索引 } } // 统计未被标记的数质数 int res 0; for (LL i L; i R; i) { if (i 2) continue; // 小于2的数不是质数 if (!st_range[i - L]) { res; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); LL L, R; cin L R; LL sqrt_R sqrt(R); sieve(sqrt_R); cout count_primes(L, R) endl; return 0; }代码解析由于 R-L≤1e6st_range 数组只需开 1e610 的大小内存占用仅 1MB 左右完全可行。计算 start 时使用(L p - 1) / p * p可以快速求出大于等于 L 的最小 p 的倍数避免了浮点数运算。4.2 例题 2UVA543 Goldbachs Conjecture题目链接https://www.luogu.com.cn/problem/UVA543题目描述验证哥德巴赫猜想任意一个大于 4 的偶数都可以拆成两个奇质数之和。对于每个输入的偶数 n输出 b-a 最大的一组解a≤ba 和 b 均为奇质数。解题思路先用线性筛法筛选出 1e6 以内的所有质数题目要求验证小于 1e6 的数。对于每个偶数 n从最小的奇质数 3 开始遍历检查 n-a 是否为奇质数。找到第一组满足条件的 (a, n-a) 即为 b-a 最大的解因为 a 越小b 越大差值越大。C 参考代码#include iostream #include cstring using namespace std; const int MAXN 1e6 10; bool st[MAXN]; int primes[MAXN], cnt; void euler_sieve(int n) { memset(st, false, sizeof st); cnt 0; for (int i 2; i n; i) { if (!st[i]) { primes[cnt] i; } for (int j 1; 1LL * i * primes[j] n; j) { st[i * primes[j]] true; if (i % primes[j] 0) { break; } } } } void solve(int n) { // 从最小的奇质数开始查找 for (int i 2; i cnt; i) { int a primes[i]; int b n - a; if (b a) continue; // 保证ab if (!st[b]) { // b是质数 printf(%d %d %d\n, n, a, b); return; } } printf(Goldbachs conjecture is wrong.\n); } int main() { euler_sieve(1e6); // 预处理1e6以内的质数 int n; while (cin n n) { solve(n); } return 0; }优化说明预处理 1e6 以内的质数后每个查询的时间复杂度为 O (π(√n))π(x) 表示 x 以内的质数个数效率极高即使处理多组数据也能快速响应。五、质数相关算法的常见误区与优化技巧5.1 常见误区整数溢出问题在计算i*p [j]或p 的幂次时容易超出 int 的范围导致程序出错。解决方案是使用 long long 类型进行中间计算。数组初始化错误筛法中数组未初始化或初始化不完全导致标记错误。建议使用 memset 函数进行初始化注意 memset 按字节赋值仅适用于 bool、char 数组或清零 int 数组。边界条件处理不当比如将 1 判定为质数、筛选时从 1 开始遍历、未处理 L1 的情况等。需要严格遵循质数的定义仔细处理边界。5.2 优化技巧内存优化对于大范围筛选如 1e8可以使用 bitset 代替 bool 数组将内存占用减少到原来的 1/8bitset 中每个元素占 1 位。输入输出优化竞赛中大数据量的输入输出会占用大量时间建议使用ios::sync_with_stdio(false);cin.tie(nullptr);或用scanf/printf代替cin/cout。预处理优化对于多组查询的题目提前预处理出最大范围的质数和相关信息如质因子、欧拉函数等避免重复计算。总结质数判定与筛法是算法竞赛数论部分的基础掌握这些技能不仅能解决直接的质数相关问题还能为后续学习质因数分解、欧拉函数、同余方程等复杂数论内容打下坚实基础。在实际竞赛中质数相关问题往往会与其他数论知识结合考查比如与欧拉函数结合的 GCD 计数问题、与中国剩余定理结合的模运算问题等。因此除了掌握本文介绍的内容还需要不断拓展知识面多做综合性题目提升知识的融会贯通能力。最后建议大家多动手实现代码通过调试理解算法的核心逻辑同时关注题目中的数据范围选择合适的算法和优化方式。只有通过大量练习才能在竞赛中快速准确地解决质数相关问题拿到关键分数。