素数筛-试除法 埃氏筛 线性筛
✨✨ 欢迎大家来到小伞的大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：算法
小伞的主页：xiaosan_bloggitee:许星让 (xu-xingrang) - Gitee.com
制作不易！点个赞吧！！谢谢喵！！
定义：
质数(素数)是指在大于 1 的**自然数**中，除了 1 和它本身以外不再有其他因数的自然数。
根据素数这一定义，可以提炼出几点内容
- 素数是自然数，因此是整数
- 素数是大于1的自然数，因此小于等于1的数字都不是素数（包括负数，0和小数）
- 素数只有两个因数，1和自身
- 结合1,2,3点，可以推断出，在自然数范围内，最小的素数是2
1.试除法
这应该是最容易想到的，我们只需要在[ 2，sqrt[n] ]范围内找到一个数，逐一枚举数字，对每一素数，尝试用n去除。
- 如果可以被整除，则说明枚举的数字是n的因子。根据素数定义，数字n非素数
- 如果不可以被整除，则需要继续往后枚举，查看其他枚举数字相除之后的结果
- 如果后面有可以被整除的数字，则结果和上面第一条一样。
- 如果在[ 2，sqrt[n] ]范围内都没有可以被整除的数字，则说明数字n在[1，n]范围内只有1和n两个因子，因此n是素数。
#define n 10010 vector<bool> isPrime(n + 1, true);//标记i位置是否为素数 void init_prime() { for (int i = 0; i < n; ++i) { if (i <= 1) isPrime[i] = false; else for (int j = 2; j <= sqrt(i); ++j) { //小于等于sqrt(i)的位置，当sqrt(i)<=j<n时，其中i%j只会在(0,1)中，所以减去多于的枚举 if (i % j == 0) { isPrime[i] = false; break; } } } }如果只对于一个数是否为素数，其中的On(sqrt(n));
1.1 剪枝
我们发现素数一定是除了2以外的奇数
#define n 10010 vector<bool> isPrime(n + 1, true);//标记i位置是否为素数 void init_prime() { for (int i = 0; i < n; ++i) { if (i <= 1) isPrime[i] = false; else if (i != 2 && i % 2 == 0) { isPrime[i] = false; } else { for (int j = 2; j <= sqrt(i); ++j) { //小于等于sqrt(i)的位置，当sqrt(i)<=j<n时，其中i%j只会在(0,1)中，所以减去多于的枚举 if (i % j == 0) { isPrime[i] = false; break; } } } } }2. 素数筛-埃氏筛(埃拉托斯特尼筛法)
一般用于对一整块的区间进行标记，用于判断多个元素,不如使用试除法+剪枝判断单个元素；
上面的朴素算法以及各种优化方法，都是对给定的单一数字进行判断，从而得知这个数字是否为素数。但在实际问题中，往往需要获取一个区间内所有素数，或者在短时间内多次查询判断。应对这样的需求，我们会进行预处理：对某一区间进行素数挑选，把素数挑选出来，存储到另外一个地方或者标记起来。
接下来介绍的这两种算法，正好是把某一区间内的素数都筛选出来，且时间复杂度也不高。
#define n 10010 vector<bool> isPrime(n + 1, true);//标记i位置是否为素数 void init_prime() { for (int i = 0; i < n; ++i) { if (i <= 1) isPrime[i] = false; else if (isPrime[i]) { for (int j = 2; i * j < n; ++j) {//我们标记存在的组合中存在最小的素数 isPrime[i * j] = false; } } } }但是这种一会存在一种弊端，当我们的值为12时，由于12=2*6=3*4，这样我们标记的时候，就会形成重复标记，会增加时间复杂度
因为我们是素数去乘以自然数，可能就会乘到不同素数的倍数，导致重复探测
3.线性筛
我们来分析一下重复标记的原因：在上面的埃式筛中，当我们遇到素数后，将它的倍数全部标记，由此可以推断：一个数被重复标记的原因是因为它是不同质数的因数。
也就是说，我们使用了多个质因数去标记了这个合数。
例如：
12被2和3标记过，30被2、3、5同时标记过。
分析出了原因，优化方向就呼之欲出了：
我们只要使用最小质因数去标记这个数（十分重要，这是线性筛的核心原理所在）就行了，具体该怎么做呢？
具体来说就是维护一个标记数组 arr 和一个已有素数数组 primes ，然后，我们从2开始遍历所有数 i ，并且：（接下来这两条好好理解！！核心部分！！）
①把遇到所有未被标记为合数的数 i （埃式筛中从小到大遍历时遇到的一个个质数）存到 primes 里去；
②以 i 为第一个因子，分别以 primes 里每个质数 j 为第二个因子，求积，可以断定 j∗i 必为合数，故标记之；同时，若 mod(i,j)==0 ，说明 j 是 i∗j 的一个质因数，又因为 primes 数组中的元素是递增的， j 是第一个可以除断 i 的，故可断定 j 是 i 的最小质因数，同时也是 i∗j 的最小质因数，那么更进一步也可断定j 之后的质数 j′ 一定不是 i∗j′ 的最小质因数，故结束 primes 的遍历。
#define n 10010 vector<bool> isPrime(n + 1, true);//标记是否为素数 vector<int> prime;//存储最小素数 void init_prime() { for (int i = 0; i <= n; ++i) { if (i <= 1) isPrime[i] = false; else { if (isPrime[i]) {//是素数 prime.push_back(i); } for (int j = 0; j < prime.size() && i * prime[j] <= n; ++j) { isPrime[i * prime[j]] = false; if (i % prime[j] == 0) break; } } } }