埃氏筛法

以一个例题引出今天的主角：

AcWing 868. 筛质数

给定一个正整数 $n_{n}$，请你求出$1∼n_{1∼n}$ 中质数的个数。

输入格式

共一行，包含整数 $n_{n}$。

输出格式

共一行，包含一个整数，表示 1∼n1∼n 中质数的个数。

数据范围

1≤n≤1061≤n≤106

输入样例：

8

输出样例：

4

解答：

c++
#include<iostream>
#include<algorithm>

using namespace std;
int cnt;
const int N = 1000010;
int primes[N];
bool st[N];

void prime(int n){
    if(n < 2){
        return;
    }
    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;
            if (i % primes[j] == 0) break;
        }
    }
}

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

分析：

时间复杂度：$O(nloglogn)$

c++
void prime(int n){
    if(n < 2){
        return;
    }
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i; //保存质数
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for (int j = 0; primes[j] <= n / i; j ++ ) {
           //p[j]一定是primes[j]*i的最小质因子，因此无需全部遍历
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
				   //防止重复筛
        }
    }
}

tips：

1. 任何一个合数都可以分解为两数相乘的形式，其中最小的质因子一定是一个质数
2. 每遇到一个数，都将其与前边的素数乘一遍，即可筛出所有的合数·
3. 为什么不需要写j<cnt
4. 当 i % primes[j] == 0 时，primes[j] 一定是 i 的最小质因子，因此 primes[j] 一定是 primes[j] * i 的最小质因子。 当 i % primes[j] != 0 时，说明i的最小质因子比primes[j]还要大，因此 primes[j] 一定是 primes[j] * i 的最小质因子。
5. 为什么要在 == 0 的时候break掉? 当 i 是 prime[j] 的倍数时，有i = k * prime[j] ，如果继续运算 j+1，i * prime[j+1] = prime[j] * k * prime[j+1] # 这里prime[j]是最小的质因子，当 i 循环到 == k * prime[j+1] 时会和 i * prime[j+1] 重复 # 所以要跳出循环。