筛素数
1:埃式筛法（简单）
原理：当枚举到一个数\(a\)得时候，我们将其的倍数都给删掉。因为这样子代表着被删掉的数除了1和其本身以外，最少还有\(a\)这个因子，故而成立。
若当枚举到一个数\(i\)的时候，\(i\)没有被删掉。因为\(i\)在之前都没有被删掉，说明从\(2 \sim i-1\)之中，没有其因子，故而其因子只有i与1，故而它是一个素数。
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if(!st[i]) primes[cnt++] = n;
for(int j = i + i;j <= n;j += i) st[j] = true;
}
}
2:埃式筛法（复杂版）
我们会发现，当我们在筛的时候，会重复特别多部分，故而我们能利用一点优化极大的提升效率：
我们可以当筛选到他的质数的时候，把他的倍数给删除，这样子也能筛选掉所有的合数。
当我们筛到第\(i\)个数的时候，该数能分解质因数为$$d_i = p_1^{a_1} * p_2^{a_2} * \ldots * p_{i-1}^{a_n} ,,,,,|,,,, \space a \subset \mathbb{N^+} ,,,,,, P_{i-1} <= d $$
故而我们可以知道当筛选到第\(i\)个数的时候，我们这个数要是是合数的话，他必定有一个质因子小于其本身\(a_i\)，故而如果我们筛到一个数他在之前没有被筛出掉，说明其质因子不小于其本身，然后分解其质因子的话，其质因子又不能大于其本身，固其质因子只有其本身。故而其约数只有1与其本身。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if(!st[i])
{
primes[cnt++] = n;
for(int j = i + i;j <= n;j += i) st[j] = true;
}
}
}
但，仔细观察，我们会发现这个算法似乎也会重复筛掉一个数字，因为设一个数为\(d\)的话，设d能分解为$$d_i = p_1^{a_1} * p_2^{a_2} * \ldots * p_{i-1}^{a_n} ,,,,,|,,,, \space a \subset \mathbb{N^+} ,,,,,, P_{i-1} <= d $$则我们可以轻易的看出，这个数会被所有\(a_n \neq 0\)的\(P_i\)项给筛一次，故而我们伟大的先人又想出一种筛法：欧拉筛法
3：欧拉筛法：
欧拉筛法的原理基于质因数分解定理，即一个数能分解为n个质因数的乘积，有了上述例子，相信我们不难理解这个定理。然后再埃式筛法的基础上，我们可以发现我们当基于素数筛的时候，我们会将一个数多筛几次，故而我们可以取一个数的一个独一无二的特征来筛除他。
这个独一无二的特征就是他的最小的质因子。
接下来这个算法要边看代码边理解才能理解比较快，比较透彻。
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
代码最主要的部分为
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
这个部分为筛素数的部分，首先再for循环的第二个参数的意义是$$primes[j] * i <= n$$ 即循环上界，然后为什么这个东西每一步操作仅仅能筛掉最小的质因子呢？
这个需要进一步理解了：
首先，这个for循环的意义是从小到达循环素数。因为是从小到大筛选的，
因为这里分为两种情况，一种是$$i \mod primes[j] != 0$$的时候 。
\(prime[j]*i\)这个数的最小质因子为\(primes[j]\)，因为在之前的筛选中，小于这个\(primes[j]\)的素数都没有筛掉这个质数，故而\(primes[j]\)为其最小质因子。
当$$i \mod primes[j] = 0$$的时候。同样的因为在之前的筛选中，小于这个\(primes[j]\)的素数都没有筛掉这个质数，故而\(primes[j]\)也是其最小质因子。
然后为什么所有合数都会被筛出来呢？
当我们筛到第\(i\)个数的时候，对于我们现在筛选到的最大素数\(P_i\)应该有\(P_i <= n_i\)然后又由于，小于 \(n_i\)的数可以分解为$$d_i = p_1^{a_1} * p_2^{a_2} * \ldots * p_{i-1}^{a_n-1} ,,,,,|,,,, \space a \subset \mathbb{N^+} ,,,,,, P_{i-1} <= d $$故而我们可以筛除掉所有合数。然后对于\(n_i\)而言我们可能将他分解为$$n_i = p_1^{a_1} * p_2^{a_2} * \ldots * p_{i-1}^{a_n-1} * p_{i}^{a_n} ,,,,,|,,,, \space a \subset \mathbb{N^+} ,,,,,, P_{i} <= n_i $$
然后如果我们的\(n_i\)是一个质数的话，我们就会发现我们从之前埃式定理的推理又派上用场了，我们筛到一个数在他之前没有被筛出掉，说明其质因子不小于其本身，然后分解其质因子的话，其质因子又不能大于其本身，固其质因子只有其本身。故而其约数只有1与其本身。
然后最重要的一点来了为什么我们筛到\(i \mod primes[j] = 0\)的话，我们就得break了呢？
这个是因为如果我们筛到\(primes[j] \mod i = 0\)的时候，我们的\(i\)的最小质因子就会为\(primes[j]\)，因而我们如果继续筛下去的话，设下一个被筛掉的数是\(d\),且\(c=\frac {i} {primes[j]}\)
我们的下一个数\(d\)就可以被分解为\(d = primes[j]*c*primes[j+1]\)这个时候就不符合我们只筛选其最小质因数的行为了。
代码：
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
欢迎收藏，欢迎订阅，欢迎关注