题目描述

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

样例

8

4

算法1

(朴素筛法)

1. cnt变量是用来记录素数的个数的，st[i]数组来判断是否是素数，i是质数则会判断成false，不是质数会被判断成true。primes[N]数组用来存放质数。
2. 不管是质数还是合数，都用来筛掉它后面的倍数。

时间复杂度

$O(nlogn)$
本质上是调和级数，所以是$O(nlnn)$，为了防止出现最坏情况，所以写成$O(nlogn)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

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

void get_primes(int 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()
{
    cin >> n;
    get_primes(n);

    cout << cnt << endl;

    return 0;
}

算法2

(埃式筛法)

1. 埃式筛法的本质是 只从质数中寻找n的约数。
2. 代码和 朴素的区别是，if的括号括的范围，直接锁定了本质—— 只从质数中寻找n的约数
3. 所以if中的for()的j是从i开始的，和上面的对应位置不同。

时间复杂度

$O(nloglogn)$
因为一个定理，1~n中有$n/ln(n)$个质数。埃式筛法的本质是 只从质数中寻找n的约数。
假设n = 2^32，表示无符号整数的最大值。那么loglogn就是5，所以时度跟$O(n)$差不多。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

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

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

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

    cout << cnt << endl;

    return 0;
}

算法3

(线性筛法)

1. n = 1e7的时候基本就比埃式筛法快一倍了。
2. 算法核心：n仅会被其最小质因子pj筛掉。
3. 当n为一个合数的时候，如果i比n / pj还小，就一定会被筛掉
4. 判断i%pj == 0，pj一定是i的最小质因子，pj也一定是pj*i最小质因子
5. 判断i%pj != 0, pj一定小于i的所有质因子，pj也一定是pj*i最小质因子
6. 对于一个合数x，假设pj是x的最小质因子，当i枚举到x / pj的时候，一定会被筛掉。
7. for(int j = 0; primes[j] <= n / i; j ++)中注意下是<=，一开始写成了<。

时间复杂度

$O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, cnt;
bool st[N];
int primes[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 ++)   // **1 '<=' 不是 '<'
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

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

    cout << cnt << endl;

    return 0;
}