红酒网站页面设计总结,教育模板网站建设,笔记转wordpress,wordpress图片尺寸#x1f31f;《素数王国的两种超级筛子》故事前言#xff1a;1、在数字王国里#xff0c;国王需要一份 素数名单。#xff08;1#xff09;比如#xff1a;1 ~ 30 之间的所有素数#xff08;2#xff09;答案应该是#xff1a;2 3 5 7 11 13 17 19 23 29#xff08;3…《素数王国的两种超级筛子》故事前言1、在数字王国里国王需要一份素数名单。1比如1 ~ 30 之间的所有素数2答案应该是2 3 5 7 11 13 17 19 23 293问题来了如果数字很大比如1 ~ 1,000,0004一个一个判断素数就会非常慢。2、于是王国发明了两种神器1️⃣埃氏筛Eratosthenes Sieve2️⃣线性筛Euler Sieve今天我们就来学习这两个神器。第一部分埃氏筛法筛沙子故事筛沙子找金子小C来到一条河边。河里有很多沙子合数和金子素数。工人拿来一个大筛子每发现一个素数就把它的倍数全部筛掉这样剩下的就都是素数。一、筛法思想1、假设我们要找1 ~ 30 的素数2、先把所有数写出来2 3 4 5 6 7 8 9 10 11 ... 303、我们准备一个数组isPrime[i]4、表示i 是否是素数5、开始全部设为true二、开始筛1、第一步2 是素数1因为 2 没被划掉。于是把2 的倍数全部划掉4 6 8 10 12 14 16 18 20 22 24 26 28 302剩下2 3 5 7 9 11 13 15 17 19 21 23 25 27 292、第二步3 是素数因为 3 没被划掉。划掉6 9 12 15 18 21 24 27 303、第三步5 是素数划掉10 15 20 25 30最后剩下2 3 5 7 11 13 17 19 23 29这些就是素数。三、为什么只筛到 √n1比如n 1002如果一个数是合数a × b n3那么一定有一个 ≤ √n 一个 ≥ √n4所以只要筛到i * i n就可以了。四、埃氏筛 C模板#include iostream using namespace std; const int N 1000000; bool isPrime[N]; int main() { int n; cin n; for(int i2;in;i) isPrime[i]true; for(int i2;i*in;i) { if(isPrime[i]) { for(int ji*i;jn;ji) isPrime[j]false; } } for(int i2;in;i) if(isPrime[i]) couti ; }五、为什么从 i*i 开始1很多同学会问为什么不是2*i2例如i 535 的倍数10 15 20 254向前看一下10 已经被 2 删过 15 已经被 3 删过 20 已经被 2 删过5所以从 25 开始可以节省时间也就是i * i六、埃氏筛时间复杂度大约是O(n log log n)已经非常快了。第二部分线性筛我们见到了一个更厉害的科学家他叫欧拉。他说我有一种方法可以让每个合数只被删一次这就是线性筛Euler筛一、线性筛思想核心思想每个合数 最小质因数 × 另一个数只用最小质因数来筛掉它。这样就不会重复删除。二、例子还是1~30我们一边走一边记录素数表1、i 22 是素数加入素数表prime {2}筛2×2 42、i 33 是素数prime {2,3}筛3×2 6 3×3 93、i 44 已经被删不是素数但继续筛4×2 84、i 55 是素数prime {2,3,5}筛5×2 10 5×3 15 5×5 255、就这样一直继续。每个合数只被最小质因数筛一次。三、线性筛 C模板#include iostream using namespace std; const int N 1000000; int prime[N]; bool vis[N]; int main() { int n; cin n; int cnt 0; for(int i2;in;i) { if(!vis[i]) prime[cnt] i; for(int j0;jcnt i*prime[j]n;j) { vis[i*prime[j]] true; if(i%prime[j]0) break; } } for(int i0;icnt;i) coutprime[i] ; }四、为什么要 break1、关键一句if(i % prime[j] 0) break;2、意思是如果prime[j]已经是i 的最小质因数3、那i × 更大的质数就不是最小质因数分解了。所以必须停止。4、这样保证每个合数只被筛一次五、时间复杂度线性筛O(n)是真正的线性时间六、两种筛法对比方法原理复杂度埃氏筛删除倍数O(n log log n)线性筛最小质因数O(n)七、理解区别1、埃氏筛1特点一个合数会被删除很多次2例如303会被2删 3删 5删2、线性筛1特点每个合数只删除一次2例如30 2 × 15只由2删除。八、什么时候用哪种筛法1、小数据n ≤ 10^6用埃氏筛简单好写。2、大数据n ≤ 10^7 或更大用线性筛更快。九、最重要的理解总结1埃氏筛思想发现素数 → 删除倍数2线性筛思想用最小质因数删除合数十、一句话记忆1埃氏筛素数 × 所有倍数2线性筛每个合数只筛一次