筛素数

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;
        }
    }
}

欢迎收藏，欢迎订阅，欢迎关注