题目描述

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

样例

输入样例：

8

输出样例：

4

比如在1到8中，有如下4个质数

1 2 3 4 5 6 7 8

1. 朴素做法 $O(nlogn)$

从2开始（因为1不是质数），每次都在n的范围内删掉自己的倍数。

第一次删掉4 6 8 …
第二次删掉6 9 12 …
…

当遍历到m，且m没有被删除时，m肯定是一个质数，因为除了1和本身外，m没有被任何数整除掉

C++ 代码

#include <iostream>

using namespace std;

const int N = 1000010;

int cnt;
int n;
bool st[N]; // 标记数组，当k是某个数的倍数时，标记st[k] = true

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
            cnt++; // 当st[i]==false时，说明之前所有数都不能整除i
        for(int j = i; j <= n; j+=i)
            st[j] = true; //当k是某个数的倍数时，标记st[k] = true
    }
}

int main()
{
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

时间复杂度 $O(nlogn)$

从2到n，一共有$\frac{n}{2}$个2的倍数
从3到n，一共有$\frac{n}{3}$个3的倍数
…
从k到n, 一共有$\frac{n}{k}$个k的倍数
…

所以标记的操作一共会执行$\frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{k} + \cdots + \frac{n}{n} = n\left(\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k} + \cdots + \frac{1}{n}\right)$
括号中的式子为调和级数的定义，将已知公式: $\displaystyle\sum_{k=1}^ n \frac{1}{k} = \ln n + c$带入 (其中c为0.577左右的无限不循环小数)
原式可以化简为$n\ln n = n\log_e n < n\log_2 n = O(nlogn)$

2. 埃氏算法 $O(n\log n \log n)$

埃氏算法是朴素算法的一个优化版本，它减少了一些标记合数的操作。
举例来说，在朴素算法中，对于数字8，既是2的倍数，也是4的倍数，所以就被标记了两遍。
在埃氏算法中，我们只标记质数的倍数，因为合数的倍数必定也是其质因子的倍数。

比如对于数字8，我们只在i=2时对其进行标记，因为4的所有倍数也都是2的倍数，不用进行重复标记。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1000010;

int cnt;
int n;
bool st[N]; 

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            cnt++; 
            for(int j = i; j <= n; j+=i) //这一行和下面
                st[j] = true;            //这一行也需要进行st[i]的判断 
        }//唯一的区别就在于这个右大括号的位置，当i是质数时才去标记它的所有倍数
    }
}

int main()
{
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

3. 线性筛法 $O(n)$

对于埃氏筛法标记操作还是会出现重复，比如12这个数，虽然不会被2、4、6重复标记，但是还是会被2、3重复标记，线性筛法在这方面做了改进，只被其最小质因子标记。下面来验证代码的正确性：

主要聚焦在下面两行代码

st[primes[j] * i] = true;
if (i % primes[j] == 0) break;

对于primes[j]*i的最小质因子，根据i是否第一次整除primes[j]分情况讨论。因为primes[j]是按照从小到大顺序排列的，所以当i第一次整除primes[j]时，primes[j]一定是i的最小质因子，因此primes[j] * i的最小质因子也一定是primes[j]. 在第一次被i整除之前, primes[j]一定小于i的所有质因子，因此primes[j] * i的最小质因子也一定是primes[j].

C++ 代码

#include <iostream>

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 = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true; //第一次i被primes[j]整除之前,primes[j]一定小于i的所有质因子
                                      //所以primes[j]一定是primes[j] * i的最小质因子
            if (i % primes[j] == 0) break; //第一次i被primes[j]整除时, primes[j]小于i的最小质因子
                                           //所以primes[j]也一定是primes[j] * i的最小质因子
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}