网站建设公司的优势,wordpress标签不显示,模板网站和定制网站的区别,为什么收不到自己网站目录 【质数和合数】 试除法判断一个数是否是质数 【埃⽒筛法】 【线性筛法】 【质数和合数】 • ⼀个⼤于 的⾃然数#xff0c;除了 和它⾃⾝外#xff0c;不能被其他⾃然数整除的数叫做质数#xff1b;否则称为合 数。其中#xff0c;质数⼜称素数。规定 1 既不是质数…目录【质数和合数】试除法判断一个数是否是质数【埃⽒筛法】【线性筛法】【质数和合数】• ⼀个⼤于 的⾃然数除了 和它⾃⾝外不能被其他⾃然数整除的数叫做质数否则称为合数。其中质数⼜称素数。规定 1 既不是质数也不是合数。试除法判断一个数是否是质数• 对于⼀个数 x 根据定义可以从 [2, x − 1] 依次拿出一个数判断 x 能否被该数整除。但是没有必要每⼀个都去判断。因为 a 如果是 的约数那么 x/a 也是 x 的约数。因此我们仅需判断较⼩的 a 是否是 x 的约数没有必要再去看看 x/a 。那么仅需枚举到根号 x 即可。bool isprime(int x) { if(x 1) return false; // ⼩于等于 1 的数不考虑 // 试除法判断是否是质数 - 只需枚举到 sqrt(x) // for(int i 2; i*i x; i) // i*i 可能溢出 for(int i 2; i x / i; i) // 防溢出的写法 { if(x % i 0) return false; } return true; }上面了解了如何判断⼀个数是否是质数如果此时想知道 [ 1 , n ] 中有多少个素数呢或者是 [ 1 , n ]中的素数⾥⾯第 k 个素数是多少• ⼀个⾃然的想法就是从 2 开始依次向后对每⼀个⾃然数进⾏⼀次质数检验。但是这种解法相对暴⼒我们这⾥介绍两种⽅法能够快速地将 [1, n] 中的素数全部记录下来。【埃⽒筛法】算法思想• 对于任意⼀个⼤于 1 的正整数 那么它的 k(k 1) 倍就是合数。因此如果我们从⼩到⼤考虑每个数然后同时把当前这个数的所有倍数记为合数没有被标记的数就是素数。⼩优化• 找到⼀个质数 x 之后可以从该数的 x 倍向后筛因此⼩于 x 的倍数⼀定被之前筛过了bool st[N]; // 当前这个数有没有被筛掉 int p[N]; // 记录质数 int cnt; // 统计质数个数 // 埃⽒筛 void get_prime() { for(LL i 2; i n; i) { if(!st[i]) // 没有被标记说明是质数 { p[cnt] i; // 记录这个质数 // 从 i*i 开始因为⼩于 i 的倍数已经被划掉了 for(LL j i * i; j n; j i) // 筛掉这个质数的倍数 { st[j] true; } } } }埃⽒筛的时间复杂度为 O(n log log n)【线性筛法】线性筛法⼜称欧拉筛法。算法思想• 在埃⽒筛法中它会将⼀个合数重复多次标记。如果能让每个合数都只被标记⼀次那么时间复杂度就可以降到 O(n*2) 了每个数最多被遍历一次和筛掉一次。我们的做法是让每⼀个合数被它的最⼩质因数筛掉。如何做到呢从前往后遍历每个数 i1、用 i 的质数倍去筛2、如果 i 是质数的倍数时停止筛遍历到下一个数bool st[N]; int p[N], cnt;// 欧拉筛 void get_prime() { for (long long i 2; i n; i) // 把 i 定义成 long long 防止溢出 { if (!st[i]) p[cnt] i; // 如果没标记过就是质数 // 用 i 的质数倍去筛 for (int j 1; i * p[j] n; j) { st[i * p[j]] true; if (i % p[j] 0) break; //如果 i 是质数的倍数时停止筛 /* 这个判定条件能让每⼀个合数被⾃⼰的最⼩质因数筛掉。 1. 如果 i 是合数枚举到最⼩质因数的时候跳出循环 2. 如果 i 是质数枚举到⾃⾝时跳出循环 注意在筛的过程中我们还能知道 p[j] 是 i 的最⼩质因数 */ } } }