$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

1.朴素筛 $O(nlogn)$

void get_primes() 
{
    for (int i = 2; i <= n; i++) 
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 2 * i; j <= n; j += i) st[j] = true; //不管是质数还是合数都把它的倍数筛掉
    }
}

2.埃氏筛 $O(nloglogn)$

void get_primes() 
{
    for (int i = 2; i <= n; i++)
        if (!st[i]) 
        {
            primes[cnt++] = i;
            for (int j = 2 * i; j <= n; j += i) st[j] = true; //只把质数的倍数筛掉
        }
}

3.线性欧拉筛 $O(n)$

// 结论：合数 n 只会被 n 的最小质因子筛掉
// 若 i % primes[j] == 0，则 primes[j] 是 i 的最小质因子
// 若 i % primes[j] != 0，则 primes[j] 小于 i 的最小质因子
// 故不论 i 是否能被 primes[j] 整除 ，primes[j] 都是 primes[j] * i 的最小质因子
// 假设 a 是 b 的最小质因子，当 i 枚举到 a / b 时，b 就会被筛掉，故每个合数都一定会被筛掉
// 并且每个数有且只有一个最小质因子，故每个数只会被筛一次

void get_primes() 
{
    for (int i = 2; i <= n; i++) 
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) 
        {
            // primes[j] 是 primes[j] * i 的最小质因子
            st[primes[j] * i] = true;

            // primes[j] 是 i 的最小质因子
            if (i % primes[j] == 0) break;
        }
    }
}

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;

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

int get_primes() 
{
    for (int i = 2; i <= n; i++) 
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) 
        {
            // primes[j] 是 primes[j] * i 的最小质因子
            st[primes[j] * i] = true;

            // primes[j] 是 i 的最小质因子
            if (i % primes[j] == 0) break;
        }
    }

    return cnt;
}

int main() 
{
    cin >> n;

    cout << get_primes() << endl;

    return 0;
}