欧拉筛法

欧拉（Euler）筛法是用于找到从$1$开始，到给定的最大数之间的所有质数的一种筛法，其时间复杂度是$O(n)$。其中欧拉筛法有效地避免了埃拉托斯特尼（Eratosthenes）筛法中重复的筛选，保证了每个数只筛选一次，成功地降低了时间复杂度。

一、埃拉托斯特尼（Eratosthenes）筛法

埃拉托斯特尼（Eratosthenes）筛法是要得到自然数$n$以内的全部质数，必须把不大于$\sqrt{n}$的所有质数的倍数剔除，剩下的就是质数。

这是因为如果是$n$合数，那么它一定有一个不大于$\sqrt{n}$的质因子，所以过了$\sqrt{n}$就不用再更新了。

具体算法为：

1. 从$2\sim \lfloor \sqrt{n}\rfloor$遍历，将质数记录在数组中；

2. 如果是质数的话，将所有这个数的倍数记录为合数；

3. 对$\lfloor \sqrt{n}\rfloor +1$到$n$进行遍历，是质数就加入数组中。

完整代码如下：

const int MAXN = 10000;
 
int cnt; //记录总共有多少个质数
int Prime[MAXN]; //记录所有质数
int NotPrime[MAXN]; //打标记
 
void Eratosthenes_Prime(int n)
{
    cnt = 0;
    memset(Prime, 0, sizeof(Prime));
    memset(NotPrime, 0, sizeof(NotPrime));
    for (int i = 2; i <= (int)sqrt(n + 0.5); ++i)
    {
        /*如果是质数，则记录下来*/
        if (!NotPrime[i])
            Prime[cnt++] = i;
        
        /*将后面质数i的倍数都记录成合数*/
        for (int j = 2; i * j <= n; ++j)
            NotPrime[i * j] = 1;
    }
    
    /*后面的用前面的质数已经筛完，直接记录*/
    for (int i = (int)sqrt(n + 0.5) + 1; i <= n; ++i)
        if (!NotPrime[i])
            Prime[cnt++] = i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

但是我们会发现，这样有一些数被筛了多次，比如$30=2\times 15=3\times 10=5\times 6$，这时候，从$2\sim n$遍历的时间复杂度是$n$，内层循环为$2$到$n/i$，$i$可以从$2$取到$\lfloor \sqrt{n}\rfloor$，所以时间复杂度为$\log \log n$，所以总的时间复杂度为$O(n\log \log n)$，产生了时间上的浪费，欧拉筛法有效地避免了其中重复的筛选。

二、欧拉（Euler）筛法

欧拉筛法的思想是每个合数只被它最小的质数筛掉，比如$30$，只被$2$筛掉，而在$3$和$5$的时候，不去判断$30$是不是合数，所以到底怎么做呢？

如果$30$被$2$筛掉，可以不去考虑在$2$的时候去筛$30$，可以在$15$的时候去筛$30$，现在我们考虑的是，这个$15$筛到什么时候停止，不再继续筛数，答案应该是到$15$中包含的最小的质因子时停止。

这是因为，对于每一个数$m=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$（其中，$p_1<p_2<\cdots <p_k$，${\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_k⩾1$，$k⩾1$），如果筛到$m\times p_1$之后继续向下筛，不妨设紧接着$p_1$之后的质数是$p_0$，即$p_0>p_1$那么就会有

$$m\times p_0=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}\times p_0=p_1\times p_1^{{\alpha }_1-1}\times p_0\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$$

这说明$m\times p_0$是可以由$p_1$筛掉的，不需要再用$p_0$去筛了。

又每一个合数$m=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$（其中，$p_1<p_2<\cdots <p_k$，${\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_k⩾1$，$k⩾2$）一定会被其最小的质因子$p_1$（即$p_1^{{\alpha }_1-1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$）筛掉，所以这种筛法满足充分性，即一定能将所有的合数都筛掉，所以欧拉筛法是一个时间复杂度为$O(n)$的算法。

所以最后的算法是：

1. 对于每个数，如果是质数，就保存下来；

2. 对于所有在约定的最大范围内的数，将这个数和之前的质因子（一直到这个数所包含的最小的质因子，之后便不再向下执行）相乘的数记录为合数。

完整代码如下：

const int MAXN = 10000;
 
int cnt; //记录总共有多少个质数
int Prime[MAXN]; //记录所有质数
int NotPrime[MAXN]; //打标记
 
void Euler_Prime(int n)
{
    cnt = 0;
    memset(Prime, 0, sizeof(Prime));
    memset(NotPrime, 0, sizeof(NotPrime));
    for (int i = 2; i <= n; ++i)
    {
        /*如果是质数，就记录下来*/
        if (!NotPrime[i])
            Prime[cnt++] = i;
        
        /*将合数筛去*/
        for (int j = 0; j < cnt; ++j)
        {
            /*超过约定的最大数就不考虑了*/
            if (i * Prime[j] > n)
                break;
            
            /*对于不超过最大的数，记录为合数*/
            NotPrime[i * Prime[j]] = 1;
            
            /*超过p1的就不考虑了，因为在别处一定筛过了*/
            if (i % Prime[j] == 0)
                break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33