题目描述

给定一个正整数n，请你求出1~n中质数的个数。

输入样例

8

输出样例

4

算法1

(朴素做法) $O(n\log{n})$

1. 先把所有的数写到一个数表中
2. 从前往后看，把每一个数的所有倍数删掉
3. 删完之后，所有剩下的数就是质数

核心原理：以p为例，如果p在最后剩下来，则从2到p-1中的任何一个数都没有把p删掉，说明p不是2到p-1中任何一个数的倍数，即满足质数定义。

时间复杂度

当$i=2$时，循环$\dfrac{n}{2}$次，当$i=3$时循环$\dfrac{n}{3}$次，因此总的循环次数为：
$$\begin{equation} \dfrac{n}{2} + \dfrac{n}{3} + \cdot\cdot\cdot + \dfrac{n}{n} = n \times (\dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}) \end{equation}$$
括号内为调和级数，当n趋近于$\infty$时，括号内的值趋近于$\ln{n}+c$，$c$是欧拉常数，为$0.577$左右的无限循环小数，因此调和级数和$\ln{n}$一个级别，因此整体的时间复杂度为$n\ln{n}$，由于底数越大，对数越小，所以$n\ln{n} < n\log_{2}{n}$，因此时间复杂度可以近似看作$n\log{n}$。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    // 从2到n枚举
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
        }
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

算法2

(优化 埃式筛法) $O(n\log\log(n))$

把循环放到判断中，不需要筛掉每一个数的倍数，只需要筛掉质数的倍数即可。
原理：按照之前的筛法留下了p，则p是一个质数，并不需要把2到p-1全部枚举，而只需要把其中的质数枚举一下即可，当一个数不是质数时，不需要筛掉它的所有倍数，由算数基本定理，每个数只要拿素数筛掉即可。

时间复杂度

粗略估计：只需要算1到n中所有的质数即可，根据质数定理，1到n中有$\dfrac{n}{\ln{n}}$个质数，朴素做法是$O(n\log{n})$，这个做法是朴素做法的$\dfrac{1}{\ln{n}}$倍。

实际：$O(n\log\log(n))$，以$2^{32}$的为例，基本上和$O(n)$一个级别。

C++ 代码

#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 ++] = i;
            for (int j = 1; j <= n; j += i) st[j] = true;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

算法3

(优化 线性筛法) $O(n)$

当数量级在$10^6$时，埃式筛和线性筛的时间复杂度差不多，当数量级在$10^7$时，线性筛比埃式筛快一倍。

核心： n只会被最小质因子筛掉
j从小到大枚举所有的质数，每次把当前的质数和i的乘积筛掉，当i模质数为0时，break，此时意味着prime[j]一定是i的最小质因子。
分情况讨论：
1. i%primes[j] == 0，primes[j]一定是i的最小质因子，即primes[j]也一定是primes[j]*i的最小质因子。
2. i%primes[j] != 0，由于是从小到大枚举的所有质数，并且没有枚举到i的任何一个质因子，因此当前的prime[j]一定是小于i的所有质因子，因此primes[j]也一定是primes[j]*i的最小质因子。

合数一定会被筛掉：对于一个合数x，假设prime[j]是x的最小质因子，当i枚举到x/prime[j]的时候， 在j循环中就会被筛掉。

线性：因为每个数只会被最小的质因子筛掉，只被筛一次，因此是线性的。

C++ 代码

#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]) prime[cnt ++] = i;
        for (int j = 0; prime[j] <= n / i; j ++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break; // prime[j]一定是i的最小质因子
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}